Non-crossing Monotonic Paths in Labeled Point Sets on the Plane
Toshinori Sakai, Jorge Urrutia · 2015
Let n be a positive integer, and let P be a set of n points in general position on the plane with la-bels 1, 2,..., n. The label of each p ∈ P will be de-noted by ℓ(p). A polygonal line connecting k elements p1, p2,..., pk of P in this order is called a monotonic path of length k if the sequence ℓ(p1), ℓ(p2),..., ℓ(pk) is monotonically increasing or decreasing in this or-der. We show that P contains a vertex set of a non-crossing monotonic path of length at least c( n − 1), where c = 1.0045.... 1