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

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(log³ n) expected amortized time, deletions take O(log⁶ n) expected amortized time, and extreme-point queries take O(log² 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).

REFERENCES

• 1: P. K. Agarwal and J. Matoušek. Dynamic half-space range reporting and its applications. Algorithmica, 13:325--345, 1995.
• 2: J. Bentley and J. Saxe. Decomposable searching problems I: static-to-dynamic transformation. J. Algorithms, 1:301--358, 1980.
• 3: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 4: Gerth Stølting Brodal , Riko Jacob, Dynamic Planar Convex Hull, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.617-626, November 16-19, 2002
• 5: Timothy M. Chan, Deterministic algorithms for 2-D convex programming and 3-D Online linear programming, Journal of Algorithms, v.27 n.1, p.147-166, April 1998 [doi>10.1006/jagm.1997.0914]
• 6: Timothy M. Chan, Dynamic planar convex hull operations in near-logarithmic amortized time, Journal of the ACM (JACM), v.48 n.1, p.1-12, Jan. 2001 [doi>10.1145/363647.363652]
• 7: Timothy M. Chan, Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions, SIAM Journal on Computing, v.30 n.2, p.561-575, 2000 [doi>10.1137/S0097539798349188]
• 8: Timothy M. Chan, Low-Dimensional Linear Programming with Violations, SIAM Journal on Computing, v.34 n.4, p.879-893, 2005 [doi>10.1137/S0097539703439404]
• 9: Timothy M. Chan, Semi-Online Maintenance of Geometric Optima and Measures, SIAM Journal on Computing, v.32 n.3, p.700-716, 2003 [doi>10.1137/S0097539702404389]
• 10: B. Chazelle. On the convex layers of a planar set. IEEE Trans. Inform. Theory, IT-31:509--517, 1985.
• 11: K. L. Clarkson. New applications of random sampling in computational geometry. Discrete Comput. Geom., 2:195--222, 1987.
• 12: Kenneth L. Clarkson , Kurt Mehlhorn , Raimund Seidel, Four results on randomized incremental constructions, Computational Geometry: Theory and Applications, v.3 n.4, p.185-212, Sept. 1993 [doi>10.1016/0925-7721(93)90009-U]
• 13: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• 14: Olivier Devillers , Stefan Meiser , Monique Teillaud, Fully dynamic Delaunay triangulation in logarithmic expected time per operation, Computational Geometry: Theory and Applications, v.2 n.2, p.55-80, Oct. 1992 [doi>10.1016/0925-7721(92)90025-N]
• 15: D. P. Dobkin and D. G. Kirkpatrick. Fast detection of polyhedral intersection. Theoret. Comput. Sci., 27:241--253, 1983.
• 16: David Dobkin , Subhash Suri, Maintenance of geometric extrema ∈ , Journal of the ACM (JACM), v.38 n.2, p.275-298, April 1991 [doi>10.1145/103516.103518]
• 17: D. Eppstein. Dynamic three-dimensional linear programming. ORSA J. Comput., 4:360--368, 1992.
• 18: D. Eppstein. Dynamic Euclidean minimum spanning trees and extrema of binary functions. Discrete Comput. Geom., 13:111--122, 1995.
• 19: David Eppstein, Fast hierarchical clustering and other applications of dynamic closest pairs, Journal of Experimental Algorithmics (JEA), 5, p.1-es, 2000 [doi>10.1145/351827.351829]
• 20: David Eppstein, Incremental and decremental maintenance of planar width, Journal of Algorithms, v.37 n.2, p.570-577, Nov. 2000 [doi>10.1006/jagm.2000.1107]
• 21: Jacob Holm , Kristian de Lichtenberg , Mikkel Thorup, Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, Journal of the ACM (JACM), v.48 n.4, p.723-760, July 2001 [doi>10.1145/502090.502095]
• 22: Jiří Matoušek, Reporting points in halfspaces, Computational Geometry: Theory and Applications, v.2 n.3, p.169-186, Nov. 1992 [doi>10.1016/0925-7721(92)90006-E]
• 23: Jiří Matoušek , Otfried Schwarzkopf, Linear optimization queries, Proceedings of the eighth annual symposium on Computational geometry, p.16-25, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142683]
• 24: J. Matoušek. On geometric optimization with few violated constraints. Discrete Comput. Geom., 14:365--384, 1995.
• 25: J. Matoušek and O. Schwarzkopf. On ray shooting in convex polytopes. Discrete Comput. Geom., 10:215--232, 1993.
• 26: Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
• 27: K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice-Hall, Englewood Cliffs, N.J., 1994.
• 28: M. H. Overmars and J. van Leeuwen. Maintenance of configurations in the plane. J. Comput. Sys. Sci., 23:166--204, 1981.
• 29: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 30: Edgar A. Ramos, On range reporting, ray shooting and k-level construction, Proceedings of the fifteenth annual symposium on Computational geometry, p.390-399, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304993]
• 31: Otfried Schwarzkopf, Dynamic maintenance of geometric structures made easy, Proceedings of the 32nd annual symposium on Foundations of computer science, p.197-206, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185369]
• 32: M. Sharir, S. Smorodinsky, and G. Tardos. An improved bound for k-sets in three dimensions. Discrete Comput. Geom., 26:195--204, 2001.

INDEX TERMS

Primary Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Design, Theory