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 language | English (US) |
---|---|
Pages | 1196-1202 |
Number of pages | 7 |
DOIs | |
State | Published - 2006 |
Externally published | Yes |
Event | Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States Duration: Jan 22 2006 → Jan 24 2006 |
Other
Other | Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|
Country/Territory | United States |
City | Miami, FL |
Period | 1/22/06 → 1/24/06 |
ASJC Scopus subject areas
- Software
- Mathematics(all)