Werner 1986

Werner proposed a two-stage algorithm [17] for finding convex hulls. The first stage takes a simple polygon and turns it into a star-shaped polygon. The second stage is just Sklansky's algorithm (1972), which is proven to work on star-shaped polygons. In the first figure below, the blue polygon is a simple polygon. The entire colored region in the second figure is the star-shaped polygon that Werner's stage 1 is supposed to compute. Notice that all new edges extend from Ymin. The polygon is a star because Ymin can see every other point of the polygon. Notice that new vertices on the boundary are created.

Werner claims that his algorithm is "short" and "simple". I ommit a description of his algorithm, since it isn't short, simple or even correct. ElGindy, who provided a counterexample [18], questions "the logic behind the operations of the ... algorithm". He provides a counterexample for which even the Sklansky scan alone would work. In fact the counterexample has only one concave vertex!

Another unatractive aspect of this algorithm is the use of Steiner points. These Steiner points can end up on the stack, which is the output of stage 1. Given that the algorithm has some rather unpredictable behavior, it wouldn't seem impossible that stage 1 actually supplies stage 2 with more than O(n) points.