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)
Content information:
Item Type: Paper (Technical Report)
Citations: [error in script] [error in script]
Uncontrolled Keywords: [error in script]
Subjects:
  • 68-XX Computer science > 68Uxx Computing methodologies and applications > 68U05 Computer graphics; computational geometry

  • 51-XX Geometry > 51Nxx Analytic and descriptive geometry > 51N20 Euclidean analytic geometry

  • Uncontrolled Keywords: convex hull, linear time algorithms, planar geometry, simple polygon
    Subjects: 68-XX Computer science > 68Uxx Computing methodologies and applications > 68U05 Computer graphics; computational geometry
    51-XX 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
    Deposit Information:
    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://e-archive.informatik.uni-koeln.de/id/eprint/160