  This paper introduces a new proximity graph, called the $k$-Semi-Yao graph
($k$-SYG), on a set $P$ of points in $\mathbb{R}^d$, which is a supergraph of
the $k$-nearest neighbor graph ($k$-NNG) of $P$. We provide a kinetic data
structure (KDS) to maintain the $k$-SYG on moving points, where the trajectory
of each point is a polynomial function whose degree is bounded by some
constant. Our technique gives the first KDS for the theta graph (\ie, $1$-SYG)
in $\mathbb{R}^d$. It generalizes and improves on previous work on maintaining
the theta graph in $\mathbb{R}^2$.
  As an application, we use the kinetic $k$-SYG to provide the first KDS for
maintenance of all the $k$-nearest neighbors in $\mathbb{R}^d$, for any $k\geq
1$. Previous works considered the $k=1$ case only. Our KDS for all the
$1$-nearest neighbors is deterministic. The best previous KDS for all the
$1$-nearest neighbors in $ \mathbb{R}^d$ is randomized. Our structure and
analysis are simpler and improve on this work for the $k=1$ case. We also
provide a KDS for all the $(1+\epsilon)$-nearest neighbors, which in fact gives
better performance than previous KDS's for maintenance of all the exact
$1$-nearest neighbors.
  As another application, we present the first KDS for answering reverse
$k$-nearest neighbor queries on moving points in $ \mathbb{R}^d$, for any
$k\geq 1$.
