Suppose we do have a set of points (all on a plane ).

  • How to find the smallest hull containing all these points ?
  • How to find the points (among these given points) that are at the exterior layers of all these points ?
  • Is there any MILP formulation for this purpose ?

enter image description here

  • 1
    $\begingroup$ Are the points on a plane like in your pictures? Or is that a higher dimensional question? For the convex hull in two dimensions you can use the gift wrapping algorithm, no need for integer programming. $\endgroup$ Oct 21 '21 at 14:53
  • $\begingroup$ They are on a plane $\endgroup$ Oct 21 '21 at 14:54
  • $\begingroup$ Then gift wrapping algorithm will find the convex hull. I am not sure what you mean by "the points that are at the exterior layer"? Do you mean the points that are inside the convex hull? Those are returned by the gift wrapping algorithm as well. $\endgroup$ Oct 21 '21 at 14:57
  • $\begingroup$ I need to find a hull (convex or non-convex) with min area to contain all the points Two examples are given in the figures, It's fine if the points are also on the borders of such a hull $\endgroup$ Oct 21 '21 at 14:59
  • $\begingroup$ Are you interested in a heuristic solution (not necessarily optimal, and definitely not provably optimal)? If so, can you post a sample data set? $\endgroup$
    – prubin
    Oct 29 '21 at 21:52

I posted a heuristic, based on a Delaunay triangulation, on my blog. Basically, you start with the triangulation, including the boundary of the convex hull. You then roam the boundary, looking for segments belonging to a triangle whose third vertex is not yet on the boundary. When you find one, you remove the segment and replace it with the other two sides of the triangle, effectively deleting the area of the triangle from the area of the enclosing polygon. This continues until a full lap around the boundary of the polygon produces no further changes.


Just a quick heuristic idea:

Step 1) I would start with determining the convex hull of the original set of points in $\mathcal O(n \log n)$ with the Graham scan. There are various implementations out there (in many languages). Robert Sedgewick has one in its book Algorithms (1983). The Java Version can be found here.

Step 2) Then I would remove the points defining the incumbent hull and determine the convex hull of the remaining points. Afterwards I would merge the incumbent hull and convex hull following a greedy approach, i.e. I would check for each pair of points whether the area defining the hull decreases and if the resulting hull still is a hull.

This approach limits the points to consider in each step and hopefully allows to determine good solutions.

One can repeat step 2 multiple times.


You can adapt the algorithm gift wrapping algorithm for finding a convex hull to this problem. This algorithm has an explicit step where it "straightens" out the cavities you want. This can be prevented by adding an additional condition that this is only allowed to happen if the new point is more left (as is done when constructing a convex hull) and closer than the proposed point (this is to prevent that the proposed point removed if it is the leftmost at his distance). This algorithm will give you the edges of the hull set. I am not aware of many LP or MILP formulations and find that approach quiet unsuited.


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.