**Next:** Problem 13: Point Location in 3D Subdivision

**Previous:** Problem 11: 3SUM Hard Problems

- Statement
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.)- Origin
Uncertain, pending investigation.

- Status/Conjectures
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.

- Partial and Related Results
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.

- Related Open Problems
- Appearances
- Categories
convex hulls; data structures

- Entry Revision History
J. O’Rourke, 2 Aug. 2001; E. Demaine, 25 Nov. 2002; 22 Aug. 2005; 24 Jan. 2006.

- [BJ02]
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.- [BJ00]
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.- [Cha99]
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.- [HS92]
J. Hershberger and S. Suri. Applications of a semi-dynamic convex hull algorithm.

*BIT*, 32:249–267, 1992.- [Jac02]
Riko Jacob.

*Dynamic Planar Convex Hull*. PhD thesis, Department of Computer Science, University of Aarhus, Aarhus, Denmark, February 2002.- [MO01]
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.- [OvL81]
M. H. Overmars and J. van Leeuwen. Maintenance of configurations in the plane.

*J. Comput. Syst. Sci.*, 23:166–204, 1981.- [Pre79]
F. P. Preparata. An optimal real-time algorithm for planar convex hulls.

*Commun. ACM*, 22:402–405, 1979.