Find simple polygons enclosing strict subset of points on a plane

Question

Given some set of black points and white points on a plane, what is a good way to find simple polygons that enclose all the black points and none of the white points?

I'm not sure what exactly I mean by "simple", but it is important as we don't want a little polygon around each black point if, for example, we could have grouped all the black points into one convex polygon without catching white points.

For lack of better ideas I'm considering merging adjacent triangles (where appropriate) from a Delaunay triangulation of the plane.

Is there any similar named problem in literature?

Answer 1

For red and blue points in general position, the paper below finds conditions where one can form a polygon connecting all the blue points and excluding all the red points.

Fulek, Radoslav, Balázs Keszegh, Filip Morić, and Igor Uljarević. "On polygons excluding point sets." Graphs and Combinatorics 29, no. 6 (2013): 1741-1753. (arXiv abs.)

---

         
          ^{Figure 1: (a) A blue polygonization excluding all the red points.}

---

Perhaps more directly relevant to your case, they prove (Theorem 8) that there exists a simple polygon with at most $3\lceil n/2 \rceil$ vertices that separates the blue from the red points. So it can be accomplished with just one polygon.

Added. In response to the OP's comments, this how I would phrase the question: Find a simple polygon $P$ enclosing blue points and excluding red points, and minimize the number of reflex vertices of $P$. This is a well-defined optimization problem, and has at least one solution (by Theorem 8). Another version would seek to minimize the perimeter of $P$, which (roughly) varies with the number of reflex vertices. This latter optimization question is known to be NP-hard:

Eades, Peter, and David Rappaport. "The complexity of computing minimum separating polygons." Pattern Recognition Letters 14.9 (1993): 715-718. (Journal link.)

Likely any reasonable formulation is NP-hard. So you should look for approximation algorithms, e.g.:

Reinbacher, Iris, Marc Benkert, Marc Van Kreveld, Joseph SB Mitchell, Jack Snoeyink, and Alexander Wolff. "Delineating boundaries for imprecise regions." Algorithmica 50, no. 3 (2008): 386-414. (Journal link.)

---