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 

Editorial actions:  View Item (Login required) 
Item Type:  Paper (Technical Report) 

Citations:  No citation data. 
Uncontrolled Keywords:  convex hull linear time algorithms planar geometry simple polygon 
Subjects: 

Divisions:  Mathematical Institute 
Related URLs: 
ZAIK Number:  zpr94160 

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 