A Long Noncrossing Path Among Disjoint Segments in the Plane
János Pach, Rom Pinchasi · 2005
Let L be a collection of n pairwise disjoint segments in general position in the plane. We show that one can find a subcollection of Ω ( n 1//3 ) segments that can be completed to a noncrossing simple path by adding rectilinear edges between endpoints of pairs of segments. On the other hand, there is a set L of n segments for which no subset of size (2 n ) 1//2 or more can be completed to such a path. 1. Introduction Since the publication of the seminal paper of Erdös and Szekeres [1935], many similar results have been discovered, establishing the existence of various regular subconfigurations in large geometric arrangements. The classical tool for proving such theorems is Ramsey theory [Graham et al. 1990]. However, the size of the regular substructures guaranteed by Ramsey's theorem are usually very small (at most logarithmic) in terms of the size n of the underlying arrangement. In most cases, the results are far from optimal. One can obtain better bounds (n ϵ for some ϵ > 0) by introducing some linear orders on the elements of the arrangement and applying some Dilworth-type theorems [1950] for partially ordered sets [Pach and Töröcsik 1994; Larman et al. 1994; Pach and Tardos 2000]. A simple onedimensional prototype of such a statement is the Erdos-Szekeres lemma: any sequence of n real numbers has a monotone increasing or monotone decreasing subsequence of length . In this note, we give a new application of this idea.