A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries

Research output: Contribution to conferencePaperpeer-review

Abstract

We present a fully dynamic randomized data structure that can answer queries about the convex hull of a set of n points in three dimensions, where insertions take O(log3 n) expected amortized time, deletions take O(log6 n) expected amortized time, and extreme-point queries take O(log2 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ε)-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).

Original languageEnglish (US)
Pages1196-1202
Number of pages7
DOIs
StatePublished - 2006
Externally publishedYes
EventSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States
Duration: Jan 22 2006Jan 24 2006

Other

OtherSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityMiami, FL
Period1/22/061/24/06

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries'. Together they form a unique fingerprint.

Cite this