$C$ is a convex object in the plane. $D_1,\dots,D_n$ are pairwise-disjoint convex subsets of $C$ such that $D_1\cup\dots\cup D_n \subsetneq C$, like this:

enter image description here

Is it always possible to partition $C$ to $n$ convex subsets, $E_1,\dots,E_n$, such that $E_1\cup\dots\cup E_n = C$, and for every $i=1,\dots,n$: $D_i \subseteq E_i$? like this:

enter image description here

EDIT: following a hint by @dxiv, here is my solution.

By the Hyperplane separation theorem, for every pair $i\neq j$ there is a line $L_{ij}$ separating $D_i$ from $D_j$. The line $L_{ij}$ divides the plane to two half-planes: one of them (call it $H_{ij}$) contains $D_i$ and the other (call it $H_{ji}$) contains $D_j$.

For every $i$, define:

$$ E_i = C \cap \left( \cap_{j\neq i} H_{ij} \right) $$

Every $E_i$ is convex since it is an intersection of convex objects.

For every $i$, $D_i\subseteq E_i$ since it is contained in $C$ and in all the half-planes in the intersection.

The $E_i$ are pairwise-disjoint since for every $i\neq j$, the half-plane $H_{ij}$ contains $E_i$ and is disjoint from $E_j$.

Problem is, the union of the $E_i$ is not equal to $C$! As seen in the illustration below (where I kept only $D_1,D_2,D_4$), there is a blue triangle which is not contained in any of the $E_i$-s:

enter image description here

  • $\begingroup$ Hint: Hyperplane separation theorem. $\endgroup$ – dxiv Feb 4 '16 at 19:07
  • $\begingroup$ @dxiv I followed your hint and found an "almost" good solution, but it is incorrect. See my edit. Do you have another hint? $\endgroup$ – Erel Segal-Halevi Feb 5 '16 at 6:11
  • $\begingroup$ N.B. I now found out that I also had a typo in the question, which may have caused some confusion. The second illustration shows correctly that the union of the $E_i$-s should be equal to $C$. But, I have written incorrectly that the union should only be contained in $C$ (this typo makes the question trivial since it is possible to take $E_i=D_i$). $\endgroup$ – Erel Segal-Halevi Feb 5 '16 at 6:13
  • $\begingroup$ I thought that was a typo. To deal with the left over "holes", I'd go along the line that at least one must have a "removable" common boundary with an $E_i$, which - after adjoining the hole - would keep $E_i$ convex, and disjoint from all others $E_j$. Then repeat until all holes have been adjoined. I haven't thought out all the gritty details, which is why I posted it as a hint and not an answer. $\endgroup$ – dxiv Feb 5 '16 at 6:41

I think you are about one step away from constructing a counterexample.

Consider your last figure. The interiors of regions $E_1$, $E_2$, and $E_4$ are pairwise disjoint convex sets whose union is a proper subset of $C$.

The only convex subsets of $C$ that contain $E_1$ and do not intersect either $E_2$ or $E_4$ are subsets of the closure of $E_1$. That is, the convex subset of $C$ must of course contain $E_1$, and it may contain some or all of the points on the boundary of $E_1$, but it cannot contain any points "above" line $L_{24}$ or to the "right" of line $L_{12}$, because inevitably there would be line segments connecting those points to points of $E_1$ while passing through either $E_2$ or $E_4$.

If you want the $D_i$ to be closed sets, then let $D_i$ be the set of all points inside the $E_i$ shown in the figure, and at least $\epsilon$ away from the boundary of $E_i$, setting $\epsilon$ small enough so that there is not enough "wiggle room" between the $D_i$ to construct convex sets containing them that look much different from the $E_i$ in the figure. In particular you can ensure that most of the area of the blue triangle continues to be impossible to include in the desired partition of $C$.

  • $\begingroup$ Thanks! I wanted the lemma to be correct, so I missed the possibility that it is incorrect :) $\endgroup$ – Erel Segal-Halevi Feb 6 '16 at 17:07

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.