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.


Actions:
Download: [img] Postscript
Download (206kB) | Preview
Export as: [error in script]
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr94-160
Depositing User: Winfried Hochstättler
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Jan 2012 11:14
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/160