Next: Problem 13: Point Location
Up: The Open Problems Project
Previous: Problem 11: 3SUM Hard
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 extremepoint 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 giftwrapping query asks to find the two vertices of the convex hull
adjacent to a given vertex of the convex hull.
A linestabbing query asks to find the two edges of the convex hull
(if any) that intersect a given line.
(Note that two extremepoint queries suffice to determine whether a line
intersects the convex hull, while a linestabbing 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 extremepoint, tangent, and giftwrapping queries
in O(log n) worstcase 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 linestabbing 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) worstcase time and
all types of queries described above in O(log n) worstcase 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+ε}n)
amortized for any
ε > 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
extremepoint, tangent, and giftwrapping 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.
 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 5770. SpringerVerlag, 2000.
 Cha99

Timothy M. Chan.
Dynamic planar convex hull operations in nearlogarithmic amortized
time.
In Proc. 40th Annu. IEEE Sympos. Found. Comput. Sci., pages
9299, 1999.
 HS92

J. Hershberger and S. Suri.
Applications of a semidynamic convex hull algorithm.
BIT, 32:249267, 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):573582, 2001.
Also in SIGACT News 32(3):6372 (2001), Issue 120.
 OvL81

M. H. Overmars and J. van Leeuwen.
Maintenance of configurations in the plane.
J. Comput. Syst. Sci., 23:166204, 1981.
 Pre79

F. P. Preparata.
An optimal realtime algorithm for planar convex hulls.
Commun. ACM, 22:402405, 1979.
Next: Problem 13: Point Location
Up: The Open Problems Project
Previous: Problem 11: 3SUM Hard
The Open Problems Project  December 04, 2015