Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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)$. –  Rahul Oct 29 '10 at 0:02
    
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. –  Qiaochu Yuan Oct 29 '10 at 0:16
    
@Rahul: the (ugly) proof I have for non-existence of cycles of length $3$ needs that the sets be convex. –  Mariano Suárez-Alvarez Oct 29 '10 at 0:28
1  
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. –  T.. Oct 29 '10 at 1:04
1  
@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). –  Tsuyoshi Ito Oct 29 '10 at 22:33

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
    
It seems to answer the question. Can it be modified to give an example with all sets disjoint? –  T.. Oct 29 '10 at 0:40
    
Ahh. I missed one important part! I'll fix the statement. –  Mariano Suárez-Alvarez Oct 29 '10 at 0:40
    
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. –  Mariano Suárez-Alvarez Oct 29 '10 at 0:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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