Why is Sklansky algorithm convex hull wrong

Question

I stumbled across this incorrect O(n) algorithm for calculating convex hulls by Sklansky, but it was later proved to be wrong.

My problem is this: why is it wrong? What is an example polygon that could give this error? Who figured it out to be wrong, and is there a paper showing it is wrong? (or does anyone have the example used to show it's wrong)

Thanks

Answer 1

Why do you think Sklansky's Convex Hull algorithm is wrong? In my personal experience, this algorithm is correct. I have used it in my projects and OpenCV also has an inbuilt function for it:

void convexHull(InputArray points, OutputArray hull, bool clockwise=false, bool returnPoints=true ) 

Note also that the complexity of Sklansky's Convex Hull algorithm is $O(N\log N)$.

Refer this paper for more details."Sklansky, J., Finding the Convex Hull of a Simple Polygon. PRL 1 $number, pp 79-83 (1982)"

Answer 2

Sklansky's 1982 algorithm was proven wrong by Touissant and El Gindy. They give counter examples in:

Toussaint, Godfried T., and Hossam El Gindy. "A counterexample to an algorithm for computing monotone hulls of simple polygons." Pattern Recognition Letters 1, no. 4 (1983): 219-222.

Counter example

Much thanks to Greg Aloupis' survey of convex hull algos: http://cgm.cs.mcgill.ca/~athens/cs601/