Next: Problem 13: Point Location in 3D Subdivision
Previous: Problem 11: 3SUM Hard Problems
Can a planar convex hull be maintained to support both dynamic updates and queries in logarithmic time? More precisely, is there a data structure supporting insertions and deletions of points and supporting various queries about the convex hull of the current set of n points, all in O(\log n) time per operation? An extreme-point query asks to find the vertex of the convex hull that is extreme in a given direction. A tangent query asks to determine whether a given point is interior to the convex hull, and if not, to find the two tangent lines of the convex hull that passes through the given point. A gift-wrapping query asks to find the two vertices of the convex hull adjacent to a given vertex of the convex hull. A line-stabbing query asks to find the two edges of the convex hull (if any) that intersect a given line. (Note that two extreme-point queries suffice to determine whether a line intersects the convex hull, while a line-stabbing query determines where exactly the line intersects the convex hull if it does.)
Uncertain, pending investigation.
Solved (in a certain sense) by Gerth Brodal and Riko Jacob in a FOCS 2002 paper [BJ02]. See also Jacob’s PhD thesis [Jac02] for further details. Their data structure supports insertions and deletions in O(\log n) amortized time and supports extreme-point, tangent, and gift-wrapping queries in O(\log n) worst-case query bounds. It remains open whether a logarithmic bound can be achieved in the worst case, and whether logarithmic bounds can be achieved (amortized or worst case) for line-stabbing queries.
For 17 years, the authority on this problem was Overmars and van Leeuwen’s paper [OvL81] which describes a data structure supporting insertions and deletions in O(\log^2 n) worst-case time and all types of queries described above in O(\log n) worst-case time. Various structures achieve faster update times when either insertions or deletions are not supported [Pre79], [HS92]. But the O(\log^2 n) barrier remained until Chan’s FOCS 1999 paper [Cha99], which improved the insertion and deletion time to O(\log^{1+\epsilon} n) amortized for any \epsilon > 0. The update time was further improved to O(\log n \log \log n) amortized by Brodal and Jacob [BJ00] until the problem was finally solved in optimal O(\log n) amortized time by the same authors [BJ02], [Jac02]. Both the Chan and the Brodal and Jacob structures support extreme-point, tangent, and gift-wrapping queries.
convex hulls; data structures
J. O’Rourke, 2 Aug. 2001; E. Demaine, 25 Nov. 2002; 22 Aug. 2005; 24 Jan. 2006.
Gerth Stølting Brodal and Riko Jacob. Dynamic planar convex hull. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, November 2002.
Gerth Stølting Brodal and Riko Jacob. Dynamic planar convex hull with optimal query time and o(\log n\cdot\log\log n) update time. In Proc. 7th Scand. Workshop Algorithm Theory, volume 1851 of Lecture Notes Comput. Sci., pages 57–70. Springer-Verlag, 2000.
Timothy M. Chan. Dynamic planar convex hull operations in near-logarithmic amortized time. In Proc. 40th Annu. IEEE Sympos. Found. Comput. Sci., pages 92–99, 1999.
J. Hershberger and S. Suri. Applications of a semi-dynamic convex hull algorithm. BIT, 32:249–267, 1992.
Riko Jacob. Dynamic Planar Convex Hull. PhD thesis, Department of Computer Science, University of Aarhus, Aarhus, Denmark, February 2002.
J. S. B. Mitchell and Joseph O’Rourke. Computational geometry column 42. Internat. J. Comput. Geom. Appl., 11(5):573–582, 2001. Also in SIGACT News 32(3):63-72 (2001), Issue 120.
M. H. Overmars and J. van Leeuwen. Maintenance of configurations in the plane. J. Comput. Syst. Sci., 23:166–204, 1981.
F. P. Preparata. An optimal real-time algorithm for planar convex hulls. Commun. ACM, 22:402–405, 1979.