Three Edge-disjoint Plane Spanning Paths in a Point Set
share
We study the following problem: Given a set S of n points in the plane, how many edge-disjoint plane straight-line spanning paths of S can one draw? A well known result is that when the n points are in convex position, ⌊ n/2⌋ such paths always exist, but when the points of S are in general position the only known construction gives rise to two edge-disjoint plane straight-line spanning paths. In this paper, we show that for any set S of at least ten points, no three of which are collinear, one can draw at least three edge-disjoint plane straight-line spanning paths of S. Our proof is based on a structural theorem on halving lines of point configurations and a strengthening of the theorem about two spanning paths, which we find interesting in its own right: if S has at least six points, and we prescribe any two points on the boundary of its convex hull, then the set contains two edge-disjoint plane spanning paths starting at the prescribed points.
READ FULL TEXT