6
$\begingroup$

Suppose that we have two disjoint triangles in the plane, then there exists a line which separates the two triangles. Is it possible to choose such a line which goes through an edge of one of the triangles.

If this is true can we generalize it to other convex polygonal shapes? Even more generally, given two disjoint bounded shapes in $\mathbb{R}^d$ defined as the intersection of hyperplanes (hence convex), can they be separated by one of their defining hyperplane?

$\endgroup$

1 Answer 1

6
$\begingroup$

Yes, this is true about two triangles $T_1,T_2$: there always exists a separating line that contains a side of $T_1$. I suspect there is a generalization to higher dimensions as you ask for, but once you see the triangle proof you can probably generalize yourself.

EDITED: See the comment of @Ofir for a counterexample in Euclidean 3-space.

To start, first one proves either the desired conclusion holds, or there exists a separating line $L$ that passes through a vertex $v_1 \in T_1$ and a vertex $v_2 \in T_2$ (the second case will be analyzed later). This can be done by starting with any separating line, and moving it parallel to itself towards $T_1$ until it first touches a point of $T_1$, hence it touches some vertex $v_1$ of $T_1$. If that line now contains one of the sides incident to $v_1$ then you're done; so we may assume it touches $T_1$ only at $v_1$. Now rotate that line around $v_1$; there are two possible directions of rotation, and the rotation angle in either direction is constrained so that $T_1$ stays on one side of the line and $T_2$ stays on the other side. In either direction of rotation, there comes a moment where one of two events happens: the line contains a second vertex of $T_1$, hence it contains a side of $T_1$ and you're done; or the line first touches $T_2$, and it must touch $T_2$ at a vertex $v_2$.

Suppose now that a separating line touches $T_1$ at a vertex $v_1$ and $T_2$ at a vertex $v_2$. Consider the segment $[v_1,v_2]$. Of the two vertices of $T_1$, pick the one $w_1$ such that the angle $\angle w_1 v_1 v_2$ is the smallest. Of the two vertices of $T_2$, pick the one $w_2$ such that the angle $\angle w_2 v_2 v_1$ is the smallest. Of those two angles $\angle w_1 v_1 v_2$ and $\angle w_2 v_2 v_1$, one of them is less than or equal to the other; by exchanging the indices $1,2$ if necessary, we may assume that $\angle w_1 v_1 v_2 \le \angle w_2 v_2 v_1$. The line through $w_1 v_1$ separates $T_1,T_2$.

$\endgroup$
2
  • $\begingroup$ By the way, this claim is not true for general dimension. For example, take the simplex $\Delta\subseteq \mathbb{R}^3$ with vertices $0,e_1,e_2,e_3$ and it opposite $-\Delta$. Now rotate $-\Delta$ around the axis $(1,1,1)$ to get a counter example. $\endgroup$
    – Ofir
    May 31, 2017 at 7:21
  • $\begingroup$ Oooh, nice example. In fact, you should post that as a separate answer. $\endgroup$
    – Lee Mosher
    Jun 1, 2017 at 18:03

You must log in to answer this question.

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