13
$\begingroup$

This was suggested by a problem on FreeNode's #math a little while ago...

Construct a directed graph $\Gamma$ with vertex set the set of compact convex sets in $\mathbb R^2$, and an arrow $A\to B$ if $A$ and $B$ are disjoint and there is a point $a$ in $A$ and a $t>0$ such that $a+(t,0)$ is in $B$.

I guess there are no oriented cycles in $\Gamma$, so it is a directed acyclic graph. Can you give a non-ugly proof?

Later: Rahul's example below shows that this is too much to hope for. In fact, what I really wanted is to know if the subgraph spanned by every finite set of disjoint convex sets has no cycles.

$\endgroup$
8
  • $\begingroup$ I conjecture that the statement remains true if you replace "convex sets" with something like "connected sets whose intersection with any line $y = \text{const}$ is either empty or an interval". This feels like the key property involved in this problem, and I imagine a proof should involve a separating "front" of the form $x = f(y)$. $\endgroup$
    – user856
    Oct 29, 2010 at 0:02
  • $\begingroup$ The obvious thing to try is to write down a monovariant, e.g. a function $\mu : \Gamma \to \mathbb{R}$ (say) such that if $A \rightarrow B$ then $\mu(A) < \mu(B)$. But it seems elusive. $\endgroup$ Oct 29, 2010 at 0:16
  • $\begingroup$ @Rahul: the (ugly) proof I have for non-existence of cycles of length $3$ needs that the sets be convex. $\endgroup$ Oct 29, 2010 at 0:28
  • 1
    $\begingroup$ For the strengthened question, it is enough to consider a Voronoi partition built from the given convex sets. I don't know if it simplifies the problem but it removes irrelevant elements from the drawings. $\endgroup$
    – T..
    Oct 29, 2010 at 1:04
  • 1
    $\begingroup$ @T..: Note that Voronoi cells in the Voronoi partition of finitely many convex sets may not be convex. (Consider a line and a point which is not on the line). $\endgroup$ Oct 29, 2010 at 22:33

2 Answers 2

9
$\begingroup$

Am I misunderstanding the conditions of the problem or is this a counterexample?

Two ellipses in an X, and two circles between them

Later: I think the answer to your updated question is yes -- or rather, no, any subgraph induced by disjoint convex sets has no cycles. (However, that would make it a directed acyclic graph or DAG, and not a tree, unless that's computer science terminology.) I have a sketch of what I think should be a valid proof, but filling in the details is a little ugly. Unfortunately, I think there is no completely non-ugly proof, for two reasons:

  1. The power of convexity is a little lost because separating hyperplanes are of no help here. If $A \rightarrow B \rightarrow C$, there is not necessarily a hyperplane separating $C$ from $A \cup B$.

  2. The proposition is not valid in more than 2 dimensions, so any proof must fundamentally depend on the 2D nature of the problem.

That said, here's the fairly ugly proof I got. Suppose for the sake of contradiction that there is a cycle of disjoint compact convex sets, $A_1 \rightarrow A_2 \rightarrow \cdots \rightarrow A_n \rightarrow A_1$. Each set $A_i$ contains a pair of points $p_i$ and $q_i$ such that $q_{i-1} \rightarrow p_i$ and $q_i \rightarrow p_{i+1}$ (where $i+1$ and $i-1$ are modulo $n$, of course). Therefore, it suffices to prove the impossibility of a cycle on the line segments $p_1 q_1 \rightarrow p_2 q_2 \rightarrow \cdots \rightarrow p_n q_n \rightarrow p_1 q_1$.

Consider the rightmost "fringe" of the first $i$ segments, as a function of $y$; that is, let $f_{i}(y) = \sup \\{x : (x,y) \in p_1 q_1 \cup p_2 q_2 \cup \cdots \cup p_i q_i\\}$. While $f_i$ is not continuous, I think you can prove by induction that if $p_1 q_1 \rightarrow p_2 q_2 \rightarrow \cdots \rightarrow p_i q_i \rightarrow p_{i+1} q_{i+1}$, then the discontinuities of $f_i$ are not "visible" to $p_{i+1}$. What I mean is that $f_i$ jumps leftwards rather than rightwards as you move in $y$ away from $p_{i+1}$, so there is no way for $q_{i+1}$ to sneak in to the left of $f_i$ without the segment $p_{i+1}q_{i+1}$ intersecting $f_i$ somewhere. Therefore, every $p_{i+1}$ and $q_{i+1}$ is to the right of $f_i$. In particular, $q_n$ is to the right of $f_{n-1}$. But $p_1$ is on or to the left of $f_{n-1}$, so $q_n \rightarrow p_1$ is impossible.

$\endgroup$
3
  • $\begingroup$ It seems to answer the question. Can it be modified to give an example with all sets disjoint? $\endgroup$
    – T..
    Oct 29, 2010 at 0:40
  • $\begingroup$ Ahh. I missed one important part! I'll fix the statement. $\endgroup$ Oct 29, 2010 at 0:40
  • $\begingroup$ I generalized to eagerly from what I wanted to what could be expected. Notice that the complete graph contains huge complete graphs: pick any set of vertices whose interiors have non-empty intersection. $\endgroup$ Oct 29, 2010 at 0:54
2
$\begingroup$

Here is a simple proof that the directed graph induced by disjoint convex sets is acyclic.

Suppose there is a counter-example, then there must be one with the smallest number of convex sets involved. Suppose such a counter example is given by the convex sets $C_1,C_2,\dots,C_n$. Then the directed cycle must contain all the $C_i$'s by the minimality assumption (otherwise just throw the ones not in the cycle away to get a smaller counter-example). WLOG, assume the graph contains $C_1\to C_2\to \cdots \to C_n\to C_1$.

Lemma: There are no other edges in this graph.

Proof: If we had $A_k\to A_r$ with $k\neq r-1 \pmod{n}$, then $A_k\to A_r\to A_{r+1}\to \cdots \to A_k$ would be a shorter cycle which contradicts our minimality assumption.

So far we haven't used that these are convex sets. Now the trick is that if there is no $A_k$ which intersects the convex hull of $A_r \cup A_{r+1}$ then substituting $A_r$ and $A_{r+1}$ with their convex hull gives a smaller collection of convex sets with a cycle.

Now by applying the lemma it follows that to show that no such $A_k$ can exist, it is enough to prove that if $A_k$ intersects the convex hull of $A_r \cup A_{r+1}$ then either $A_r \to A_k$ or $A_k \to A_{r+1}$, but this is obvious if you draw the picture, so I'll leave it as an exercise :)

Since there are no two convex sets $A\to B \to A$, we are done.

$\endgroup$

You must log in to answer this question.

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