### A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queriesA dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries

Access Restriction
Subscribed

 Author Chan, Timothy M. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2010 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Computational geometry ♦ Convex hulls ♦ Dynamic data structures ♦ Nearest neighbor search Abstract We present a fully dynamic randomized data structure that can answer queries about the convex hull of a set of $\textit{n}$ points in three dimensions, where insertions take $O(log^{3}n)$ expected amortized time, deletions take $O(log^{6}n)$ expected amortized time, and extreme-point queries take $O(log^{2}n)$ worst-case time. This is the first method that guarantees polylogarithmic update and query cost for arbitrary sequences of insertions and deletions, and improves the previous $O(n^{&epsis;})-time$ method by Agarwal and Matoušek a decade ago. As a consequence, we obtain similar results for nearest neighbor queries in two dimensions and improved results for numerous fundamental geometric problems (such as levels in three dimensions and dynamic Euclidean minimum spanning trees in the plane). ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2010-03-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 57 Issue Number 3 Page Count 15 Starting Page 1 Ending Page 15

#### Open content in new tab

Source: ACM Digital Library