Note on noncrossing path in colored convex sets
Viola Mészáros, Peter I. Hajnal · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · 2010
Consider a 2n element colored point set, n points red and n points blue, in convex position in the plane.Erdős asked to estimate the number of points in the longest noncrossing path such that edges join points of different color and are straight line segments.Kynčl, Pach and Tóth in 2008 gave a construction proving the upper bound 4 3 n + O( √ n).This bound is conjectured to be tight.For an arbitrary coloring they gave a lower bound n + Ω( n log n ).In this paper we improve the previous lower bound to n + Ω( √ n).We also present a class of configurations that shows the 4 3 n + O( √ n) upper bound.