1
$\begingroup$

$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

$\endgroup$
4
  • $\begingroup$ Hint: Hyperplane separation theorem. $\endgroup$
    – dxiv
    Feb 4, 2016 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$ Feb 5, 2016 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$ Feb 5, 2016 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, 2016 at 6:41

1 Answer 1

3
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ Thanks! I wanted the lemma to be correct, so I missed the possibility that it is incorrect :) $\endgroup$ Feb 6, 2016 at 17:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .