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)


  • $\begingroup$ A. Bykat, Convex hull of a finite set of points in two dimensions, pp. 296-298. $\endgroup$ – Cave Johnson Feb 2 '18 at 13:16
  • $\begingroup$ I can't find a copy of that paper $\endgroup$ – code base 5000 Feb 2 '18 at 13:34
  • $\begingroup$ There were two algorithms by Slansky, both incorrect. Which one do you mean? $\endgroup$ – Professor Vector Feb 2 '18 at 13:56
  • 2
    $\begingroup$ The first page of Bykat's paper is freely available at doi.org/10.1016/0020-0190(78)90021-2 $\endgroup$ – lhf Feb 2 '18 at 14:38

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.