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