Kinetic Data Structures for the Semi-Yao Graph and All Nearest Neighbors in $\mathbb{R}^d$.
Zahed Rahmati, Mohammad Ali Abam, Valerie Jean King, Sue H. Whitesides · arXiv (Cornell University) · 2013
This paper presents kinetic data structures (KDS’s) for maintaining the Semi-Yao graph, all the nearest neighbors, and all the (1 + )-nearest neighbors of a set of moving points in R. Our technique provides the first KDS for the SemiYao graph in R. It generalizes and improves on the previous work on maintaining the Semi-Yao graph in R. Our KDS for all nearest neighbors is deterministic. The best previous KDS for all nearest neighbors in R is randomized. Our structure and analysis are simpler and improves on the previous work. Finally, we provide a KDS for all the (1 + )-nearest neighbors, which in fact gives better performance than the exact KDS’s for all nearest neighbors.