next up previous
Next: Problem 37: Counting Polyominoes Up: The Open Problems Project Previous: Problem 35: Freeze-Tag: Optimal


Problem 36: Inplace Convex Hull of a Simple Polygonal Chain

Statement
How much extra space is required to compute the convex hull of a simple polygonal chain or simple polygon in linear time?

More precisely, given the n points in order along the chain in an array A, the alogorithm must re-arrange the points inplace in the array and output a number h so that the first h elements in the resulting array are the points on the convex hull in order. The goal is to minimize the extra storage past the array A, say to O(log n) or ideally O(1).

Origin
[BIK+01]
Status/Conjectures
Solved [BC04].
Partial and Related Results
From the abstract of [BC04]: ``we present a simple self-contained solution that uses O(log n) space, and indicate how to improve it to O(1) space with the same techniques used for stable partition.''
Appearances
Posed in [BIK+01], and by Hervé Brönnimann during the open problem session at the Fall Workshop on Computational Geometry, Brooklyn, NY, Nov. 2-3, 2001.
Categories
convex hulls
Entry Revision History
E. Demaine, 21 Nov. 2001; J. O'Rourke, 10 Mar. 2004 (thanks to Ryan Coleman).

Bibliography

BC04
Hervé Brönnimann and Timothy Chan.
Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time.
In Proceedings of the 6th Latin American Symposium on Theoretical Informatics, volume 2976 of Lecture Notes in Computer Science, pages 162-171, 2004.

BIK+01
Hervé Brönnimann, John Iacono, Jryki Katajainen, Pat Morin, and Jason Morrison.
Optimal in-place planar convex hull algorithms.
11th Annu. Fall Workshop Comput. Geom., 2001.
http://geometry.poly.edu/cgwpapers/.


next up previous
Next: Problem 37: Counting Polyominoes Up: The Open Problems Project Previous: Problem 35: Freeze-Tag: Optimal
The Open Problems Project - December 04, 2015