Problem 12: Dynamic Planar Convex Hull

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²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²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 loglog 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

Problem 63.

Appearances

[MO01]

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.

Bibliography

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 ^. loglog 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.