Résumé : 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 $L$ is a sequence $p_1, ..., p_L$ of $L$ points from $P$ so that (i) all points are pairwise distinct; (ii) any two consecutive points $p_i, p_{i+1}$ have different colors; and (iii) any two segments $p_i p_{i+1}$ and $p_j p_{j+1}$ have disjoint relative interiors, for $i \neq j$. We show that there is an absolute constant $\epsilon > 0$, independent of $n$ and of the coloring, such that $P$ always admits a non-crossing alternating path of length at least $(1 + \epsilon)n$. The result is obtained through a slightly stronger statement: there always exists a non-crossing bichromatic separated matching on at least $(1 + \epsilon)n$ points of $P$. This is a properly colored matching whose segments are pairwise disjoint and intersected by a 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)$. Based on joint work with Pavel Valtr.

 [Slides.pdf] [article]

Dernière modification : Monday 18 March 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr