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

Research output: Contribution to journalArticlepeer-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(log3n) expected amortized time, deletions take O(log6n) expected amortized time, and extreme-point queries take O(log2n) 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 Matouek 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)
Article number16
JournalJournal of the ACM
Volume57
Issue number3
DOIs
StatePublished - Mar 1 2010
Externally publishedYes

Keywords

  • Computational geometry
  • Convex hulls
  • Dynamic data structures
  • Nearest neighbor search

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

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