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

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.     

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.     

On approximation behavior of the greedy triangulation for convex polygons

We prove that the greedy triangulation heuristic for minimum weight triangulation of convex polygons yields solutions within a constant factor from the optimum. For interesting classes of convex polygons, we derive small upper bounds on the constant approximation factor. Our results contrast with Kirkpatrick's (n) bound on the approximation factor of the Delaunay triangulation heuristic for minimum weight triangulation of convexn-vertex polygons. On the other hand, we present a straightforward implementation of the greedy triangulation heuristic for ann-vertex convex point set or a convex polygon takingO(n ²) time andO(n) space. To derive the latter result, we show that given a convex polygonP, one can find for all verticesv ofP a shortest diagonal ofP incident tov in linear time. Finally, we observe that the greedy triangulation for convex polygons having so-called semicircular property can be constructed in timeO(n logn).     

On the ultimate convex hull algorithm in practice

Kirkpatrick and Seidel [13,14] recently proposed an algorithm for computing the convex hull of n points in the plane that runs in O(n log h) worst case time, where h denotes the number of points on the convex hull of the set. Here a modification of their algorithm is proposed that is believed to run in O(n) expected time for many reasonable distributions of points. The above O(n log h) algorithmsare experimentally compared to the O(n log n) ‘throw-away’ algorithms of Akl, Devroye and Toussaint [2, 8, 20]. The results suggest that although the O(n Log h) algorithms may be the ‘ultimate’ ones in theory, they are of little practical value from the point of view of running time.     

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.     

On geodesic properties of polygons relevant to linear time triangulation

Triangulating a simple polygon ofn vertices inO(n) time is one of the main open problems in computational geometry. The fastest algorithm to date, due to Tarjan and van Wyk, runs inO(n log logn), but several classes of simple polygons have been shown to admit linear time traingulation. Famous examples of such classes are: star-shaped, monotone, spiral, edge visible, and weakly externally visible polygons. The notion of geodesic paths is used here to characterize all classes of polygons for which linear time triangulation algorithms are known. First we introduce a new class of polygons,palm polygons, which subsumes many known classes of polygons for which linear time triangulation algorithms exist, and present a linear time algorithm for triangulating polygons in this class. Then a class of polygons,crab polygons, is defined and shown to contain all classes of existing polygons for which linear time triangulation algorithms are known. As a byproduct of this characterization, a new, very simple linear time algorithm for triangulating star-shaped polygons is obtained.Research supported by Faculty of Graduate Studies and Research (McGill University) and NSERC under grant OGP0036737Research supported by FCAR grant EQ-1678 and NSERC grant A9293     

A linear time algorithm for computing the convex hull of an ordered crossing polygon

In this paper, we describe a linear time algorithm for finding the convex hull of an ordered crossing polygon and prove its correctness.     

A counterexample to an algorithm for computing monotone hulls of simple polygons

A two-stage algorithm was recently proposed by Sklansky (1982) for computing the convex hull of a simple polygon P. The first step is intended to compute a simple polygon $\text{P}{}^1$ which is monotonic in both the x and y directions and which contains the convex hull vertices of P. The second step applies a very simple convex hull algorithm on $\text{P}{}^1$. In this note we show that the first step does not always work correctly and can even yield non-simple polygons, invalidating the use of the second step. It is also shown that the first step can discard convex hull vertices thus invalidating the use of any convex hull algorithm in the second step.     

Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons

Given a triangulation of a simple polygonP, we present linear-time algorithms for solving a collection of problems concerning shortest paths and visibility withinP. These problems include calculation of the collection of all shortest paths insideP from a given source vertexS to all the other vertices ofP, calculation of the subpolygon ofP consisting of points that are visible from a given segment withinP, preprocessingP for fast "ray shooting" queries, and several related problems.Work on this paper by this author has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, the IBM Corporation, and from the U.S.-Israel Binational Science Foundation.Work on this paper by this author has been supported by National Science Foundation Grant DCR-86-05962.     

An efficient algorithm for decomposing a polygon into star-shaped polygons

In this paper we show how a theorem in plane geometry can be converted into a O(n log n) algorithm for decomposing a polygon into star-shaped subsets. The computational efficiency of this new decomposition contrasts with the heavy computational burden of existing methods.     

Optimal parallel algorithms for point-set and polygon problems

In this paper we give parallel algorithms for a number of problems defined on point sets and polygons. All our algorithms have optimalT(n) * P(n) products, whereT(n) is the time complexity andP(n) is the number of processors used, and are for the EREW PRAM or CREW PRAM models. Our algorithms provide parallel analogues to well-known phenomena from sequential computational geometry, such as the fact that problems for polygons can oftentimes be solved more efficiently than point-set problems, and that nearest-neighbor problems can be solved without explicitly constructing a Voronoi diagram.The research of R. Cole was supported in part by NSF Grants CCR-8702271, CCR-8902221, and CCR-8906949, by ONR Grant N00014-85-K-0046, and by a John Simon Guggenheim Memorial Foundation fellowship. M. T. Goodrich's research was supported by the National Science Foundation under Grant CCR-8810568 and by the National Science Foundation and DARPA under Grant CCR-8908092.     

A new linear algorithm for triangulating monotone polygons

Let P = (p₁, p₂,…,p_n) be a monotone polygon whose vertices are specified in terms of cartesian coordinates in order. A new simple two-step procedure is presented for triangulating P, without the addition of new vertices, in O(n) time. Unlike the previous algorithm no specialized code is needed since the new approach uses well-known existing algorithms for first decomposing P into edge-visible polygons and subsequently triangulating these.     

A linear-time algorithm for constructing a circular visibility diagram

To computer circular visibility inside a simple polygon, circular arcs that emanate from a given interior point are classified with respect to the edges of the polygon they first intersect. Representing these sets of circular arcs by their centers results in a planar partition called the circular visibility diagram. AnO(n) algorithm is given for constructing the circular visibility diagram for a simple polygon withn vertices.     

MP稀疏分解快速算法及其在语音识别中的应用

提出一种新的基于Matching Pursuit（MP）的语音信号稀疏分解算法。在对语音信号稀疏分解中使用的过完备原子库进行划分的基础上,将内积运算转换成互相关运算,并结合语音信号与原子是实的特性,利用Fast Hartley Transform（FHT）快速实现互相关运算。从而比利用FFT实现基于MP的信号稀疏分解节省一半的存储空间,提高分解速度约24.8%。此外,应用改进后的算法对语音信号进行特征提取,并结合语音信号的美尔（Mel）频率倒谱参数一起作为该信号的特征向量,通过Support Vector Machine（SVM）进行识别,最后通过实验验证了方法的有效性。     

Using parallel line information for vision-based landmark location estimation and an application to automatic helicopter landing

An approach to landmark location estimation by computer vision techniques is proposed. The objective is to derive the position and the orientation of the landmark with respect to the vehicle by a single image. Such information is necessary for automatic vehicle navigation. This approach requires lower hardware cost and simple computation. The vanishing points of the parallel lines on the landmark are used to detect the landmark orientation. The detected vanishing points are used to derive the relative orientation between the landmark and the camera, which is then utilized to compute the landmark orientation with respect to the vehicle. The size of the landmark is used to determine the landmark position. Sets of collinear points are extracted from the landmark and their inter-point distances are computed. The positions of the collinear point sets are evaluated and used to determine the landmark position. Landing site location estimation by using the identification marking H on the helicopter landing site for automatic helicopter landing is presented as an application of the proposed approach. Simulations and experiments have been conducted to prove the feasibility of the proposed approach.