3 added 7 characters in body

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

2 deleted 6 characters in body

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 polygons in its interior, find a decomposition of $P$ into convex polygons such that no such convex region 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

1

# Decomposing a polygon with holes

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 polygons in its interior, find a decomposition of $P$ into convex polygons such that no such convex region 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