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

A. Bykat, Convex hull of a finite set of points in two dimensions, pp. 296-298. — Cave Johnson, Feb 02 '18 at 13:16
There were two algorithms by Slansky, both incorrect. Which one do you mean? — , Feb 02 '18 at 13:56
The first page of Bykat's paper is freely available at https://doi.org/10.1016/0020-0190(78)90021-2 — lhf, Feb 02 '18 at 14:38

score 2 · Answer 1 · answered Jan 06 '20 at 02:56

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/

score 0 · Answer 2 · edited Apr 02 '19 at 15:36

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)"

Why is Sklansky algorithm convex hull wrong

2 Answers2