Can I read Kinetic Data Structures for the Semi-Yao Graph and All Nearest Neighbors in R^d on EtoBox?

Kinetic Data Structures for the Semi-Yao Graph and All Nearest Neighbors in R^d by Rahmati, Zahed; Abam, Mohammad Ali; King, Valerie; Whitesides, Sue is a scholarly article available to read on EtoBox.

What is Kinetic Data Structures for the Semi-Yao Graph and All Nearest Neighbors in R^d about?

This paper presents a simple kinetic data structure for maintaining all the nearest neighbors of a set of $n$ moving points in $\mathbb{R}^d$, where the trajectory of each point is an algebraic function of at most constant degree $s$. The approach is based on maintaining the edges of the Semi-Yao graph, a sparse graph whose edge set includes the pairs of nearest neighbors as a subset. Our kinetic data structure (KDS) for maintaining all the nearest neighbors is deterministic. It processes $O(n^2\beta_{2s+2}^2(n)\log n)$ events with a total cost of $O(n^2\beta_{2s+2}(n)\log^{d+1} n)$. Here, $\beta_s(n)$ is an extremely slow-growing function. The best previous KDS for all the nearest neighbors in $ \mathbb{R}^d$ is by Agarwal, Kaplan, and Sharir (TALG 2008). It is a randomized result. Our structure and analysis are simpler than theirs. Also, we improve their result by a factor of $\log^d n$ in the number of events and by a $\log n$ factor in the total cost. This paper generalizes and improves the 2013 work of Rahmati, King and Whitesides (SoCG 2013) on maintaining the Semi-Yao graph in $\mathbb{R}^2$; its new technique provides the first KDS for the Semi-Yao graph in $\mathbb{R}^d$.

Author

Rahmati, Zahed; Abam, Mohammad Ali; King, Valerie; Whitesides, Sue

Published

2013

Language

EN