# Long alternating paths exist

### Wednesday, November 11th, 16:10

### Wolfgang Mulzer, FU Berlin

### Abstract:

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 /= j.

We show that there is an absolute constant eps > 0, independent of n and

of the coloring, such that P always admits a non-crossing alternating

path of length at least (1 + eps)n. The result is obtained through a

slightly stronger statement: there always exists a non-crossing

bichromatic separated matching on at least (1 + eps)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.

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 /= j.

We show that there is an absolute constant eps > 0, independent of n and

of the coloring, such that P always admits a non-crossing alternating

path of length at least (1 + eps)n. The result is obtained through a

slightly stronger statement: there always exists a non-crossing

bichromatic separated matching on at least (1 + eps)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.