Tight bounds for dynamic convex hull queries (again)

ABSTRACT

The dynamic convex hull problem was recently solved in O(lg n) time per operation, and this result is best possible in models of computation with bounded branching (e.g., algebraic computation trees). From a data structures point of view, however, such models are considered unrealistic because they hide intrinsic notions of information in the input.In the standard word-RAM and cell-probe models of computation, we prove that the optimal query time for dynamic convex hulls is, in fact, Theta(lg n / lglg n), for polylogarithmic update time (and word size). Our lower bound is based on a reduction from the marked-ancestor problem, and is one of the first data structural lower bounds for a nonorthogonal geometric problem. Our upper bounds follow a recent trend of attacking nonorthogonal geometric problems from an information-theoretic perspective that has proved central to advanced data structures. Interestingly, our upper bounds are the first to successfully apply this perspective to dynamic geometric data structures, and require substantially different ideas from previous work.

REFERENCES

• 1: Stephen Alstrup , Thore Husfeldt , Theis Rauhe, Marked Ancestor Problems, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.534, November 08-11, 1998
• 2: Lars Arge , Jeffrey Scott Vitter, Optimal External Memory Interval Management, SIAM Journal on Computing, v.32 n.6, p.1488-1508, 2003 [doi>10.1137/S009753970240481X]
• 3: Michael A. Bender , Richard Cole , Erik D. Demaine , Martin Farach-Colton , Jack Zito, Two Simplified Algorithms for Maintaining Order in a List, Proceedings of the 10th Annual European Symposium on Algorithms, p.152-164, September 17-21, 2002
• 4: J.L. Bentley and J.B. Saxe. Decomposable searching problems i: Static-to-dynamic transformation. Journal of Algorithms, 1(4):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: 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
• 7: C. Burnikel , R. Fleischer , K. Mehlhorn , S. Schirra, Efficient exact geometric computation made easy, Proceedings of the fifteenth annual symposium on Computational geometry, p.341-350, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304988]
• 8: Timothy M. Chan, Dynamic Planar Convex Hull Operations in Near-Logarithmic Amortized Time, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.92, October 17-18, 1999
• 9: Timothy M. Chan, Point Location in o(log n) Time, Voronoi Diagrams in o(n log n) Time, and Other Transdichotomous Results in Computational Geometry, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), p.333-344, October 21-24, 2006 [doi>10.1109/FOCS.2006.62]
• 10: T.M. Chan and M. Patrascu. Voronoi diagrams in n · 2^{O(√lg lg n)} time. In Proceedings of the 39th ACM Symposium on Theory of Computing, San Diego, California, June 2007.
• 11: Mark de Berg , Marc van Kreveld , Jack Snoeyink, Two- and three-dimensional point location in rectangular subdivisions, Journal of Algorithms, v.18 n.2, p.256-277, March 1995 [doi>10.1006/jagm.1995.1010]
• 12: P. Dietz , D. Sleator, Two algorithms for maintaining order in a list, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.365-372, January 1987, New York, New York, United States [doi>10.1145/28395.28434]
• 13: James R. Driscoll , Neil Sarnak , Daniel D. Sleator , Robert E. Tarjan, Making data structures persistent, Journal of Computer and System Sciences, v.38 n.1, p.86-124, February 1989 [doi>10.1016/0022-0000(89)90034-2]
• 14: Michael L. Fredman , Dan E. Willard, Trans-dichotomous algorithms for minimum spanning trees and shortest paths, Journal of Computer and System Sciences, v.48 n.3, p.533-551, June 1994 [doi>10.1016/S0022-0000(05)80064-9]
• 15: L.J. Guibas and D.H. Marimont. Rounding arrangements dynamically. International Journal of Computatinal Geometry and Applications, 8(2):157--176, 1998.
• 16: Yijie Han , Mikkel Thorup, Integer Sorting in 0(n sqrt (log log n)) Expected Time and Linear Space, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.135-144, November 16-19, 2002
• 17: R. Jacob. Dynamic Planar Convex Hull. PhD thesis, Department of Computer Science, University of Aarhus, Aarhus, Denmark, February 2002.
• 18: V. Karamcheti , C. Li , I. Pechtchanski , C. Yap, A core library for robust numeric and geometric computation, Proceedings of the fifteenth annual symposium on Computational geometry, p.351-359, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304989]
• 19: K. Mehlhorn and S. Schirra. Exact computation with leda_real -- theory and geometric applications. In Symbolic Algebraic Methods and Verification Methods, pages 163--172. Springer, January 2001.
• 20: J. Nievergelt and E.M. Reingold. Binary search trees of bounded balance. SIAM Journal on Computing, 2:33--43, 1973.
• 21: M.H. Overmars. Computational geometry on a grid: an overview. In Theoretical Foundations for Computer Graphics and CAD, pages 167--184. Springer-Verlag, 1988.
• 22: M.H. Overmars and J. van Leeuwen. Maintenance of configurations in the plane. Journal of Computer and System Sciences, 23(2):166--204, 1981.
• 23: Eli Packer, Iterated snap rounding with bounded drift, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137910]
• 24: Mihai Patrascu, Planar Point Location in Sublogarithmic Time, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), p.325-332, October 21-24, 2006 [doi>10.1109/FOCS.2006.61]
• 25: Jonathan Richard Shewchuk, Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator, Selected papers from the Workshop on Applied Computational Geormetry, Towards Geometric Engineering, p.203-222, May 27-28, 1996
• 26: A.M. Turing. On computable numbers with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Series 2, 42:230--265, August 1936.
• 27: Andrew Chi-Chih Yao, Should Tables Be Sorted?, Journal of the ACM (JACM), v.28 n.3, p.615-628, July 1981 [doi>10.1145/322261.322274]
• 28: C. Yap. Theory of real computation according to EGC. In Proceedings of the Dagstuhl Seminar on Reliable Implementation of Real Number Algorithms: Theory and Practice, Lecture Notes in Computer Science, 2006. To appear. http://www.cs.nyu.edu/exact/doc/realtheory.pdf.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

General Terms:
Algorithms, Performance, Theory

Keywords:
bounded precision, dynamic convex hull, word RAM