Definition of convex layers can be found at wikipedia.
I was trying to understand this algorithm , which works in O(n log n) time, which is optimal.

In the paper, the author has described two types of deletions, among which one is direct deletion.

In direct deletions, the author deletes the a point of the previous Convex Layer, from the Hull Graph( an endemic concept). The author has written something about Direct Deletions that I didn't understand:

" In general, a pulling operation will be accomplished by conceptually replaying the previous two pulling operations. This replay might be necessary in order to guide the current tangent on it's way down, and in particular find at little cost the vertices over which it must fold."

Hull Graph: A union of the upper(resp. lower) chains of the subsets of vertices of the given set of points.
Pulling operation: Deletion of edges that are connected to the vertex to be deleted in the hull graph(called tangents).

I would like to know how can the line in bold be accomplished. Moreover, there's a keen interest of mine to implement this algorithm. Would that be irrational, given the hardness of this algorithm?


Any reasonable help about this paper is appreciated.


  • $\begingroup$ You might want to implement simple convex hull algorithm rerun it after removing the points on convex hull. If thats too slow for you then you might want to implement this one. $\endgroup$ – Pratik Deoghare Dec 29 '16 at 5:53
  • $\begingroup$ @Pratik Yeah, that's always an option. But still, I would like to know how this one works, at least. Implementing is an option which comes in hand after I understand it completely. $\endgroup$ – Mooncrater Dec 29 '16 at 6:04

Your Answer

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

Browse other questions tagged or ask your own question.