The convex hull of a point set is a well understood problem and nice optimal solutions are known in the case of a finite point set and a simple polygon.

For a convex polygon, the hull is the polygon itself. When it is concave, the difference is made of "pockets" which are also polygonal regions, and you can iterate until all pockets are convex.

I am wondering if there is any theory about this process and an efficient algorithm to construct the hierarchy, possibly as a generalization of Melkman's algorithm?

Convex hull sample

  • 1
    $\begingroup$ @evil: your edit made the whole sentence incorrect. $\endgroup$ – Yves Daoust Oct 26 '17 at 22:37
  • $\begingroup$ What hierarchy are you referring to? What are the nested convex hulls? I understand you want to compute teh convex hull of a concave polygon, but I'm not sure where the nesting comes in. Can you explain? Haven't you already described an algorithm? I might be missing something obvious. $\endgroup$ – D.W. Oct 27 '17 at 4:12
  • $\begingroup$ @D.W.: you should understand what I mean by pockets. They are illustrated in the picture (green, then orange, then yellow). Blindly applying the convex hull algorithm to the successive pockets is probably a waste because you don't reuse results from previous steps. I am wondering what the theoretical complexity can be. $\endgroup$ – Yves Daoust Oct 27 '17 at 6:16

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.