Next: Problem 37: Counting Polyominoes
Previous: Problem 35: Freeze-Tag: Optimal Strategies for Awakening a Swarm of Robots
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).
Solved [BC04].
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.”
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.
convex hulls
E. Demaine, 21 Nov. 2001; J. O’Rourke, 10 Mar. 2004 (thanks to Ryan Coleman).
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.
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/.