Access Restriction

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

   Open content in new tab
Source: ACM Digital Library