Non-crossing Monotone Paths and Cycles through Specified Points of Labeled Point Sets

Discrete and Computational Geometry, Graphs, and Games

Abstract

Let $P$ be a set of $n$ points in convex position in the plane, each of which is assigned a different number, called a label. A path whose vertices are points of $P$ is called monotone if the labels of its vertices increase while traversing it starting from one of its end vertices. We show that for any element $q \in P$, there is a non-crossing monotone path containing $q$ connecting at least $\bigl\lceil \sqrt{2(n-1)}\, \bigr\rceil$ elements. This bound is almost tight. A simple polygon with vertices in $P$ is called monotone if it consists of a monotone path and the line segment connecting its endpoints. The polygon is monotonically increasing (respectively decreasing) if when we traverse it in the clockwise direction starting at one of its vertices, the labels of its vertices increase (respectively decrease). We call such a simple polygon an increasing (respectively a decreasing) cycle. We also prove that any set $P$ of $(l-1)(m-1)+2$ labeled points in general position in the plane, and for any point $q \in P$ on the boundary of the convex hull of $P$, there exists an increasing cycle containing $q$ with at least $l+1$ elements, or a decreasing cycle containing $q$ with at least $m+1$ elements.