  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 $\ell$ is a sequence $p_1, \dots, p_\ell$ of $\ell$ 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 $\varepsilon > 0$, independent of
$n$ and of the coloring, such that $P$ always admits a non-crossing alternating
path of length at least $(1 + \varepsilon)n$. The result is obtained through a
slightly stronger statement: there always exists a non-crossing bichromatic
separated matching on at least $(1 + \varepsilon)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)$.

Computational Geometry;Discrete Mathematics;Combinatorics