Time- and storage-efficient implementation of an optimal planar convex hull algorithm

An implementation of an algorithm for computing the convex hull of a finite planar set of points is presented. The program is compared with an algorithm for the same purpose coded previously. Experimental results indicate that our program is superior to the other in terms of both running time and storage requirements.     

On the conditions for success of sklansky''s convex hull algorithm

The convex hull algorithm for simple polygons, due to Sklansky, fails in some cases, but its extreme simplicity, compared to the later algorithms, revived an interest in this algorithm. A sufficient condition for its success was given recently by Toussaint and Avis. They have proved that the algorithm works for polygons known as weakly externally visible polygons.

In this paper a new notion called external left visibility is introduced and it is shown that this is a necessary and sufficient condition for the success of Sklansky's algorithm. Moreover, algorithms testing simple polygons for external left visibility and weak external visibility are given.     

平面点集凸壳的一种近似算法

提出了一种计算海量平面点集凸壳的快速近似算法——点集坐标旋转法(PSCR)。该算法采用点集不断旋转并求X(Y)坐标极值的方法得到平面点集的近似凸壳。它充分利用了成熟的数据库技术,能够在比较短的时间内计算出海量平面点集的近似凸壳。它不需要空间索引的支持,并能获得比较理想的近似效果。     

Finding the convex hull of a simple polygon

We describe a new algorithm for finding the convex hull of any simple polygon specified by a sequence of m vertices.An earlier convex hull finder of ours is limited to polygons which remain simple (i.e., nonselfintersecting) when locally non-convex vertices are removed. In this paper we amend our earlier algorithm so that it finds with complexity O(m) the convex hull of any simple polygon, while retaining much of the simplicity of the earlier algorithm.     

A linear time algorithm for obtaining the convex hull of a simple polygon

In this paper, a linear time algorithm is described for finding the convex hull of a simple (i.e. non-self intersecting) polygon.     

Finding the convex hull of a simple polygon in linear time

Though linear algorithms for finding the convex hull of a simply-connected polygon have been reported, not all are short and correct. A compact version based on Sklansky's original idea⁽⁷⁾ and Bykat's counter-example⁽⁸⁾ is given. Its complexity and correctness are also shown.     

A convex hull algorithm for planar simple polygons

A linear convex hull algorithm which is an improvement on the algorithm due to Sklansky is given.     

On a convex hull algorithm for polygons and its application to triangulation problems

A frequently used algorithm for finding the convex hull of a simple polygon in linear running time has been recently shown to fail in some cases. Due to its simplicity the algorithm is, nevertheless, attractive. In this paper it is shown that the algorithm does in fact work for a family of simple polygons known as weakly externally visible polygons. Some application areas where such polygons occur are briefly discussed. In addition, it is shown that with a trivial modification the algorithm can be used to internally and externally triangulate certain classes of polygons in 0(n) time.     

A fast convex hull algorithm with maximum inscribed circle affine transformation

This paper presents a fast convex hull algorithm for a large point set. The algorithm imitates the procedure of human visual attention derived in a psychological experiment. The merit of human visual attention is to neglect most inner points directly. The proposed algorithm achieves a significant saving in time and space in comparison with the two best convex hull algorithms mentioned in a latest review proposed by Chadnov and Skvortsov in 2004. Furthermore, we propose to use an affine transformation to solve the narrow shape problem for computing the convex hull faster.     

On the application of the convex hull to histogram analysis in threshold selection

A recently proposed algorithm for computing the convex hull of a grey-level histogram in image segmentation is shown to be inefficient due to the fact that it does not exploit the histogram's structure. It is pointed out that a histogram is a weakly externally visible polygon and thus a very simple linear convex hull algorithm will work for such applications.     

The complexity of incremental convex hull algorithms in Rd

The complexity of any incremental convex hull algorithm in R^d is shown to be $\text{Ω(n}{}^{\mathrm{<mtext>[</mtext><mtext>(d+1)</mtext><mtext>2</mtext><mtext>]</mtext>}}\text{)}$ for n points and constant d.     

Numerical stability of a convex hull algorithm for simple polygons

A numerically stable and optimalO(n)-time implementation of an algorithm for finding the convex hull of a simple polygon is presented. Stability is understood in the sense of a backward error analysis. A concept of the condition number of simple polygons and its impact on the performance of the algorithm is discussed. It is shown that if the condition number does not exceed (1+O())/(3), then, in floating-point arithmetic with the unit roundoff, the algorithm produces the vertices of a convex hull for slightly perturbed input points. The relative perturbation does not exceed 3(1+O()).J. W. Jaromczyk was partially supported by a grant from the Center for Robotics and Manufacturing Systems at the University of Kentucky and G. W. Wasilkowski was partially supported by the National Science Foundation under Grants CCR-89-05371 and CCR-91-14042.