# How to find the point on the exterior of a given set of points?

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 ?

• 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. Oct 21, 2021 at 14:53
• They are on a plane Oct 21, 2021 at 14:54
• 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. Oct 21, 2021 at 14:57
• 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 Oct 21, 2021 at 14:59
• Are you interested in a heuristic solution (not necessarily optimal, and definitely not provably optimal)? If so, can you post a sample data set?
– prubin
Oct 29, 2021 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.