  For a set of $n$ points in the plane, this paper presents simple kinetic data
structures (KDS's) for solutions to some fundamental proximity problems,
namely, the all nearest neighbors problem, the closest pair problem, and the
Euclidean minimum spanning tree (EMST) problem. Also, the paper introduces
KDS's for maintenance of two well-studied sparse proximity graphs, the Yao
graph and the Semi-Yao graph.
  We use sparse graph representations, the Pie Delaunay graph and the
Equilateral Delaunay graph, to provide new solutions for the proximity
problems. Then we design KDS's that efficiently maintain these sparse graphs on
a set of $n$ moving points, where the trajectory of each point is assumed to be
an algebraic function of constant maximum degree $s$. We use the kinetic Pie
Delaunay graph and the kinetic Equilateral Delaunay graph to create KDS's for
maintenance of the Yao graph, the Semi-Yao graph, all the nearest neighbors,
the closest pair, and the EMST. Our KDS's use $O(n)$ space and $O(n\log n)$
preprocessing time.
  We provide the first KDS's for maintenance of the Semi-Yao graph and the Yao
graph. Our KDS processes $O(n^2\beta_{2s+2}(n))$ (resp.
$O(n^3\beta_{2s+2}^2(n)\log n)$) events to maintain the Semi-Yao graph (resp.
the Yao graph); each event can be processed in time $O(\log n)$ in an amortized
sense. Here, $\beta_s(n)$ is an extremely slow-growing function.
  Our KDS for maintenance of all the nearest neighbors and the closest pair
processes $O(n^2\beta^2_{2s+2}(n)\log n)$ events. For maintenance of the EMST,
our KDS processes $O(n^3\beta_{2s+2}^2(n)\log n)$ events. For all three of
these problems, each event can be handled in time $O(\log n)$ in an amortized
sense.
  We improve the previous randomized kinetic algorithm for maintenance of all
the nearest neighbors by Agarwal, Kaplan, and Sharir, and the previous EMST KDS
by Rahmati and Zarei.
