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

作     者：Brönnimann, H Chan, TM 

作者机构：Polytech Univ Dept Informat & Comp Sci Brooklyn NY 11201 USA Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada 

出 版 物：《COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS》 (计算几何学)

年 卷 期：2006年第34卷第2期

页      面：75-82页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：National Science Foundation  NSF  (CCR-0133599  CCR-0133599) 

主　　题：computational geometry convex hull space-efficient algorithm 

摘      要：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 in-place stable partition, i.e., if there were a truly simple solution then in-place 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, the problem admits a very simple solution which does not call for stable partitioning at all. (c) 2005 Elsevier B.V. All rights reserved.