Question

It is known that given a polygon $P$ with holes it is NP-hard to find a decomposition of $P$ into convex polygons, s.t. their number is minimized (even if Steiner points are allowed).

I am wondering if anything is known about the following problem:

Given a convex polygon $P$ which contains a collection $\mathcal{Q}$ of convex polygons in its interior, find a decomposition of $P$ into convex polygons such that no such polygon contains more than one polygon from $\mathcal{Q}$ and the number of convex polygons is minimized.

In the example below, $P$ is the black polygon, $\mathcal{Q}$ are the four blue polygons, and the red linesegments induce a convex partitioning of $P$ where each face contains at most one polygon from $\mathcal{Q}$ .

http://i48.tinypic.com/2h7402h.png

Answer 1

I haven't worked out the details but this seems very likely to be NP-complete. The reduction I have in mind uses the following ideas:

• You can arrange three convex holes in such a way that the lines that separate one hole from another are very tightly constrained, so that it's not possible to separate all three pairs of holes from each other by three lines that meet in a single point. When this happens, it forces any partition into convex sets to include a fourth convex set (above the three convex sets containing the three holes), in the middle area between the three holes.

• With a little more care you can set up systems of four holes, with two roughly-triangular areas loosely surrounded by three of the four holes, in such a way that you are forced to include a fifth convex set (above the four convex sets containing the four holes) in one of these two triangular areas, but you get to choose which of the two triangular areas to put the fifth convex set into.

• Minimum dominating set is NP-complete for planar graphs, even if all vertices have degree at most three and even if there is some $k$ such that all degree-three vertices are separated from each other by paths of length at least $k$ (this is because subdividing edges into long paths of odd length changes the dominating set size in a predictable way). Using the four-hole gadgets described above to represent edges, it should be possible to reduce this special planar dominating set problem to your problem.

Answer 2

I don't know of an algorithm for your specific problem. But if your polygonal holes are well-separated in the sense that their convex hulls are disjoint (as in your example—and now the OP edited to specify convex holes), then you might be able to adapt cluster-partition algorithms to your task. The figure below, which I extracted from a paper by Li et al., "On cluster tree for nested and multi-density data clustering," Pattern Recognition, 2010 (Elsevier link), illustrates my suggestion:

---