A fully dynamic algorithm for planar

ABSTRACT

We show how to maintain the width of a set of $n$ planar points subjec t to insertions and deletions of points in $O(\sqrt{n}\log^3n)$ amortized time per update. Previously, no fully dynamic algorithm with a guaranteed sublinear time bound was known.

REFERENCES

• 1: P. K. Agarwal and J. Matousek. Dynamic half-space range reporting and its applications. Algorithmica, 13:325-345, 1995.
• 2: Pankaj K. Agarwal , Micha Sharir, Off-line dynamic maintenance of the width of a planar point set, Computational Geometry: Theory and Applications, v.1 n.2, p.65-78, Sept. 1991 [doi>10.1016/S0925-7721(00)00026-2]
• 3: A. Aggarwal , L. J. Guibas , J. Saxe , P. W. Shor, A linear-time algorithm for computing the Voronoi diagram of a convex polygon, Discrete & Computational Geometry, v.4 n.6, p.591-604, Sep. 1989 [doi>10.1007/BF02187749]
• 4: J. Bentley and J. Saxe. Decomposable searching problems I: static-to-dynamic transformation. J. Algorithms, 1:301-358, 1980.
• 5: 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
• 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: B. Chazelle. On the convex layers of a planar set. IEEE Trans. Inform. Theory, IT-31:509-517, 1985.
• 8: D. Eppstein. Dynamic three-dimensional linear programming. ORSA J. Comput., 4:360-368, 1992.
• 9: D. Eppstein. Dynamic Euclidean minimum spanning trees and extrema of binary functions. Discrete Comput. Geom., 13:111-122, 1995.
• 10: David Eppstein, Average case analysis of dynamic geometric optimization, Computational Geometry: Theory and Applications, v.6 n.1, p.45-68, April 1996 [doi>10.1016/0925-7721(95)00018-6]
• 11: 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]
• 12: 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]
• 13: R. Janardan. On maintaining the width and diameter of a planar point-set online. Int. J. Comput. Geom. Appl., 3:331-344, 1993.
• 14: Jiří Matoušek, Linear optimization queries, Journal of Algorithms, v.14 n.3, p.432-448, May 1993 [doi>10.1006/jagm.1993.1023]
• 15: M. H. Overmars and J. van Leeuwen. Maintenance of configurations in the plane. J. Comput. Sys. Sci., 23:166-204, 1981.
• 16: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 17: G. Rote, C. Schwarz, and J. Snoeyink. Maintaining the approximate width of a set of points in the plane. In Proc. 5th Canad. Conf. Comput. Geom., pages 258-263, 1993.
• 18: Kenneth J. Supowit, New techniques for some dynamic closest-point and farthest-point problems, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.84-90, January 22-24, 1990, San Francisco, California, United States
• 19: G. T. Toussaint. Solving geometric problems with the rotating calipers. In Proc. Mediterranean Electrotechnical Conf., pages 1-4, 1983.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Design, Theory