Dynamic planar convex hull operations in near-logarithmic amortized time

ABSTRACT

We give a data structure that allows arbitrary insertions and deletions on a planar point set P and supports basic queries on the convex hull of P, such as membership and tangent-finding. Updates take O(log1+&egr;n) amori tzed time and queries take O (log n time each, where n is the maximum size of P and &egr; is any fixed positive constant. For some advanced queries such as bridge-finding, both our bounds increase to O(log3/2n). The only previous fully dynamic solution was by Overmars and van Leeuwen from 1981 and required O(log2n) time per update and O(log n) time per query.

REFERENCES

• 1: Pankaj K. Agarwal , Mark de Berg , Jirí Matousek , Otfried Schwarzkopf, Constructing Levels in Arrangements and Higher Order Voronoi Diagrams, SIAM Journal on Computing, v.27 n.3, p.654-667, June 1998 [doi>10.1137/S0097539795281840]
• 2: AGARWAL, P. K., AND MATOUSEK, J. 1995. Dynamic half-space range reporting and its applications. Algorithmica 13, 325-345.
• 3: AGARWAL, P. K., AND SHARIR, M. 2000. Arrangements and their applications. In Handbook of Computational Geometry, J. Urrutia and J. Sack, eds. North-Holland, Amsterdam, The Netherlands.
• 4: ANDRZEJAK, A., AND WELZI., E. 1997. k-sets and j -facets: A tour of discrete geometry. Manuscript.
• 5: Julien Basch , Leonidas J. Guibas , G. D. Ramkumar, Reporting Red-Blue Intersections between Two Sets of Connected Line Segments, Proceedings of the Fourth Annual European Symposium on Algorithms, p.302-319, September 25-27, 1996
• 6: BENTLEY, J., AND SAXE, J. 1980. Decomposable searching problems. I: Static-to-dynamic transformation. J. Algorithms 1, 301-358.
• 7: B~HRINGER, K.-F., DONALD,B.R.,AND HALPERIN, D. 1999. On the area bisectors of a polygon. Disc. Comput. Geom. 22, 269-285.
• 8: Gerth Stølting Brodal , Riko Jacob, Dynamic Planar Convex Hull with Optimal Query Time, Proceedings of the 7th Scandinavian Workshop on Algorithm Theory, p.57-70, July 05-07, 2000
• 9: CHAN, T. M. 1996. Output-sensitive results on convex hulls, extreme points, and related problems. Disc. Comput. Geom. 16, 369-387.
• 10: CHAN, T. M. 1999. Remarks on k-level algorithms in the plane. Manuscript.
• 11: 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]
• 12: CHAZELLE, B. 1985. On the convex layers of a planar set. IEEE Trans. Inf. Theory IT-31, 509-517.
• 13: B. Chazelle , H. Edelsbrunner, An improved algorithm for constructing kth-order voronoi diagrams, IEEE Transactions on Computers, v.36 n.11, p.1349-1354, Nov. 1987
• 14: CHIANG, Y.-J., AND TAMASSIA, R. 1992. Dynamic algorithms in computational geometry. Proc. IEEE 80, 1412-1434.
• 15: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 16: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 17: DEVILLERS, O., AND KATZ, M. J. 1999. Optimal line bipartitions of point sets. Int. J. Comput. Geom. Appl. 1, 39-51.
• 18: David P. Dobkin , David Eppstein , Don P. Mitchell, Computing the discrepancy with applications to supersampling patterns, ACM Transactions on Graphics (TOG), v.15 n.4, p.354-376, Oct. 1996 [doi>10.1145/234535.234536]
• 19: DOBKIN, D. P., AND KIRKPATRICK, D. G. 1983. Fast detection of polyhedral intersection. Theoret. Comput. Sci. 27, 241-253.
• 20: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 21: EDELSBRUNNER, H., AND WELZI., E. 1986. Constructing belts in two-dimensional arrangements with applications. SIAM J. Comput., 15, 271-284.
• 22: J. Friedman , J. Hershberger , J. Snoeyink, Efficiently Planning Compliant Motion in thePlane, SIAM Journal on Computing, v.25 n.3, p.562-599, June 1996 [doi>10.1137/S0097539794263191]
• 23: Sherif Ghali , A. James Stewart, Maintenance of the set of segments visible from a moving viewpoint in two dimensions, Proceedings of the twelfth annual symposium on Computational geometry, p.503-504, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237423]
• 24: Sariel Har-Peled, Taking a Walk in a Planar Arrangement, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.100, October 17-18, 1999
• 25: John Hershberger , Subhash Suri, Finding tailored partitions, Journal of Algorithms, v.12 n.3, p.431-463, Sept. 1991 [doi>10.1016/0196-6774(91)90013-O]
• 26: John Hershberger , Subhash Suri, Applications of a semi-dynamic convex hull algorithm, BIT, v.32 n.2, p.249-267, 1992 [doi>10.1007/BF01994880]
• 27: John Hershberger , Subhash Suri, Off-line maintenance of planar configurations, Journal of Algorithms, v.21 n.3, p.453-475, Nov. 1996 [doi>10.1006/jagm.1996.0054 ]
• 28: JANARDAN, R. 1993. On maintaining the width and diameter of a planar point-set online. Int. J. Comput. Geom. Appl. 3, 331-344.
• 29: KAPOOR, S. 1998. Dynamic maintenance of 2-d convex hulls and order decomposable problems. Manuscript.
• 30: MATOUSEK, J. 1995. On geometric optimization with few violated constraints. Disc. Comput. Geom. 14, 365-384.
• 31: Nimrod Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms, Journal of the ACM (JACM), v.30 n.4, p.852-865, Oct. 1983 [doi>10.1145/2157.322410]
• 32: Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
• 33: Ketan Mulmuley, Randomized multidimensional search trees: lazy balancing and dynamic shuffling (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.180-196, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185368]
• 34: MULMULEY, K. 1994. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice-Hall, Englewood Cliffs, N.J.
• 35: Mark H. Overmars, Design of Dynamic Data Structures, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
• 36: OVERMARS, M. H., AND VAN LEEUWEN, J. 1981. Maintenance of configurations in the plane. J. Comput. Sys. Sci. 23, 166-204.
• 37: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 38: 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]
• 39: ROTE, G., SCHWARZ, C., AND SNOEYINK, J. 1993. Maintaining the approximate width of a set of points in the plane. In Proceedings of the 5th Canadian Conference on Computational Geometry, pp. 258-263.
• 40: 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]

INDEX TERMS

Primary Classification:
  E. Data

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

General Terms:
Algorithms, Theory

Keywords:
computational geometry, convex hulls, dynamic data structures