Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
Suppose we do have a set of points (all on a plane ).
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.
