A new Linear Time Algorithm for Computing the Convex Hull of a Simple Polygon in the Plane
Hochstättler, Winfried and Kromberg, Stephan and Moll, Christoph
(1994)
A new Linear Time Algorithm for Computing the Convex Hull of a Simple Polygon in the Plane.
Technical Report
, 12 p.
Abstract
The problem of determining the convex hull of a simple polygon has received a lot of attention in the early eighties. The first linear time algorithm for this task proposed by Sklansky [IEEE Trans. Comput. 21 (1972)] was based on the simple idea of removing all left turns while moving around the polygon in clockwise orientation. This algorithm was shown to fail in some cases. Since then several correct, yet more complicated linear algorithms have been published and classes of polygons have been determined for which Sklansky's original algorithm can be used. In our note we show how to mend Sklansky's Algorithm in a simple way and prove the correctness of the resulting algorithm. As an application we show how to compute a rectangle of smallest area containing a given simple polygon in linear time.
Download: 
Postscript
Download (206kB)  Preview 

Export as:  [error in script] 
Editorial actions:  View Item (Login required) 
Item Type:  Paper (Technical Report) 

Citations:  [error in script] [error in script] 
Uncontrolled Keywords:  [error in script] 
Subjects: 

Uncontrolled Keywords:  convex hull, linear time algorithms, planar geometry, simple polygon 
Subjects:  68XX Computer science > 68Uxx Computing methodologies and applications > 68U05 Computer graphics; computational geometry 51XX Geometry > 51Nxx Analytic and descriptive geometry > 51N20 Euclidean analytic geometry 
Divisions:  Mathematical Institute 
Depositing User:  Winfried Hochstättler 
Date Deposited:  02 Apr 2001 00:00 
Last Modified:  19 Jan 2012 11:14 
ZAIK Number:  [error in script] 

Depositing User:  Winfried Hochstättler 
Date Deposited:  02 Apr 2001 00:00 
Last Modified:  19 Jan 2012 11:14 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/160 