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 line segments induce a convex partitioning of $P$ where each face contains at most one polygon from $\mathcal{Q}$ .



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.

  • $\begingroup$ @David Eppstein Thank you for your reduction idea. What is not clear to me is the meaning of the placement of the fifth convex set into the four-hole gadgets. Did you mean that it indicates which vertex of the edge is contained in the dominating set? But what confuses me is that not every edge has an endpoint in the DS. $\endgroup$ – steve Aug 4 '12 at 11:37
  • $\begingroup$ What I meant is that when you decompose the four-hole gadget into convex subsets, you have to use five subsets, one of which does not contain any hole. This extra empty subset must lie inside one of the two triangular regions surrounded by the four holes, but you get to choose which of these two regions it lies in. $\endgroup$ – David Eppstein Aug 11 '12 at 0:38

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:

         Cluster Partition

  • $\begingroup$ @Joseph O'Rourke Thank you for your answer, I will look if I can borrow something from the ML community :-) and sorry for the later editing, but the "holes" may really be convex in my application. $\endgroup$ – steve Aug 2 '12 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.