TY - CHAP

T1 - Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time

AU - Brönnimann, Hervé

AU - Chan, Timothy M.

N1 - Funding Information:
✩ A preliminary version of this paper appeared under same title and authors in Proc. Latin American Conference on Theoretical Informatics (LATIN), 2004, pp. 162–171. * Corresponding author. E-mail addresses: [email protected] (H. Brönnimann), [email protected] (T.M. Chan). 1 Research of the first author supported by NSF CAREER Grant CCR-0133599. 2 Research of the second author supported in part by an NSERC Research Grant.

PY - 2004

Y1 - 2004

N2 - We present space-efficient algorithms for computing the convex hull of a simple polygonal line in-place, in linear time. It turns out that the problem is as hard as stable partition, i.e., if there were a truly simple solution then stable partition would also have a truly simple solution, and vice versa. Nevertheless, 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. If the points inside the convex hull can be discarded, then there is a truly simple solution that uses a single call to stable partition, and even that call can be spared if only extreme points are desired (and not their order). If the polygonal line is closed, then the problem admits a very simple solution which does not call for stable partitioning at all.

AB - We present space-efficient algorithms for computing the convex hull of a simple polygonal line in-place, in linear time. It turns out that the problem is as hard as stable partition, i.e., if there were a truly simple solution then stable partition would also have a truly simple solution, and vice versa. Nevertheless, 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. If the points inside the convex hull can be discarded, then there is a truly simple solution that uses a single call to stable partition, and even that call can be spared if only extreme points are desired (and not their order). If the polygonal line is closed, then the problem admits a very simple solution which does not call for stable partitioning at all.

UR - http://www.scopus.com/inward/record.url?scp=35048875720&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35048875720&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-24698-5_20

DO - 10.1007/978-3-540-24698-5_20

M3 - Chapter

AN - SCOPUS:35048875720

SN - 3540212582

SN - 9783540212584

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 162

EP - 171

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Farach-Colton, Martin

PB - Springer

ER -