2020/03/30 by Mulzer, Wolfgang, Valtr, Pavel · 1 citation
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2003.13291
Let P be a set of 2n points in convex position, such that n points are colored red and n points are colored blue. A non-crossing alternating path on P of length ℓ is a sequence p1, …, p_ℓ of ℓ points from P so that (i) all points are pairwise distinct; (ii) any two consecutive points pi, pi+1 have different colors; and (iii) any two segments pi pi+1 and pj pj+1 have disjoint relative interiors, for i ≠ j. We show that there is an absolute constant ε > 0, independent of n and of the coloring, such that P always admits a non-crossing alternating path of length at least (1 + ε)n. The result is obtained through a slightly stronger statement: there always exists a non-crossing bichromatic separated matching on at least (1 + ε)n points of P. This is a properly colored matching whose segments are pairwise disjoint and intersected by common line. For both versions, this is the first improvement of the easily obtained lower bound of n by an additive term linear in n. The best known published upper bounds are asymptotically of order 4n/3+o(n).