Intersection of paths connecting vertices of convex hull

70 Views Asked by At

Suppose we have a set of $n$ points, and suppose that the convex hull of those points contains vertices $i$, $j$, $k$, and $l$, appearing in that order on the convex hull but not necessarily consecutively.

Suppose further that we draw a path from $i$ to $k$ and another path from $j$ to $l$, both paths being contained within the convex hull.

It seems evident to me that the two paths must intersect, but I'm unable to come up with a simple proof. Any ideas?

2

There are 2 best solutions below

1
On BEST ANSWER

Start of an argument. Consider the region whose "top" edge is the boundary of the convex set from $i$ to $k$ and whose "bottom" edge is the path from $k$ to $i$.

The convexity implies that the path from $j$ to $l$ starts out inside that region and ends up outside. Then the Jordan curve theorem tells you it crosses the boundary. That crossing must be at the bottom edge.

Possible subtleties:

You may need to work a little harder if the bottom edge has self intersections.

Treat the case when three of $ijkl$ are collinear separately.

2
On

$i$ is on one side of $\overline{jk}$ and $l$ is on the other side of $\overline{jk}$. The definition of convexity is that if $i$ and $l$ are in the set, the straight line joining them is in the set.

QED.