A new linear convex hull algorithm for simple polygons (Corresp.)
- 1 January 1984
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 30 (1) , 85-88
- https://doi.org/10.1109/tit.1984.1056845
Abstract
A new optimal algorithm for computing the convex hull of a simple polygon in the plane, along with a proof of correctness, is presented. The main novelty of the proposed algorithm is its use of existing concepts such as the unimodality of the area of a triangle inscribed in a convex polygon and Sldansky's scan. The combination of these concepts gives us new insight into the problem.Keywords
This publication has 12 references indexed in Scilit:
- An efficient algorith for determining the convex hull of a finite planar setPublished by Elsevier ,2002
- On a convex hull algorithm for polygons and its application to triangulation problemsPattern Recognition, 1982
- Finding the convex hull of a simple polygonPattern Recognition Letters, 1982
- On the multimodality of distances in convex polygonsComputers & Mathematics with Applications, 1982
- Some aspects of convexity useful in information theoryIEEE Transactions on Information Theory, 1980
- On a general method for maximizing and minimizing among certain geometric problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Convex hull of a finite set of points in two dimensionsInformation Processing Letters, 1978
- A fast convex hull algorithmInformation Processing Letters, 1978
- Divide and conquer for linear expected timeInformation Processing Letters, 1978
- Measuring Concavity on a Rectangular MosaicIEEE Transactions on Computers, 1972