Personal tools
You are here: Home CG seminar 2021 Long alternating paths exist
« December 2020 »
Log in

Forgot your password?

Long alternating paths exist

Wednesday, November 11th, 16:10


Wolfgang Mulzer, FU Berlin


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.
Document Actions