Find smallest irregular polygon from combination of vertices (Performance Critical)

Question

I need to find an irregular polygon with the smallest surface area out of several vertices on a 2D plane.

No this isn't homework. Although I wish I was back in school right now.

There are some requirements on how the polygon can be constructed. Let's say I have 3 different types of vertices (red, green, blue) plotted out on a 8x8 grid. I need to scan all vertices in this grid satisfying the red, green, blue combination requirement and pick the one with the smallest surface area.

Getting the surface area of an irregular polygon is simple enough. I'm mainly concerned about the performance of scanning all possible combinations efficiently.

See the below image for an example. All three types are used to make the polygons however the one circled has the smallest surface area and is my objective.

This scenario is simplified compared to what I'm trying to prototype. The polygons will be constructed of tens if not hundreds of vertices and the grid will be much larger. Also, this will be a process ran 24/7.

I was thinking that maybe I should organize the vertices by type and break them into individual arrays. Then just iterate over the arrays in a tiered fashion to compute the surface area of all combinations. This approach however seems wasteful.

Answer 1

Here is a version based on branch and bound, with some flourishes.

1) Break the grid down into a Quadtree, with annotations in the nodes as needed for the rest.

2) Find the lowest node in the quad tree that has one of each type of node. This gives you a starting solution, which should be at least good enough to speed up the rest of the search.

3) Do a recursive search which takes all possible branches where I say guess, choosing the most promising candidates first where applicable:

3a) Guess a vertex of the least common type.

3b) Using the relative location of points in the quad tree to order your guesses, guess a vertex of the next least common type, so as to guess them in increasing order of distance form the original point...

3z) you have a complete set of vertices.

At each step 3? you have a partial set of vertices, which I presume gives you a lower bound on the area of any complete solution including those vertices (is it the area inside the convex hull of the vertices?). You can discard any partial solutions that are already at least as large as the largest solutions so far. If you can live with an answer that is X% inaccurate, you can discard any partial solutions that are within X% of the largest solution so far. Hopefully this prunes the tree of possibilies you are navigating in (3) far enough to make it tractable.