A New Linear Time Algorithm for Computing the Convex Hull of a Simple Polygon
Winfried Hochstättler, S. Kromberg, Christoph Moll · 1994
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 was proposed by Sklansky (1972). Sklansky’s Algorithm can be described as follows: Start at an extreme point of the polygon. Delete all left turns while moving around the polygon in clockwise direction. After each step backtrack until the path from the starting point to the point currently considered given by the not (yet) deleted points has right turns only. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.