Mulzer, Wolfgang ;
Valtr, Pavel
Long Alternating Paths Exist
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 noncrossing alternating path on P of length 𝓁 is a sequence p₁, … , p_𝓁 of 𝓁 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 ε > 0, independent of n and of the coloring, such that P always admits a noncrossing alternating path of length at least (1 + ε)n. The result is obtained through a slightly stronger statement: there always exists a noncrossing bichromatic separated matching on at least (1 + ε)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).
BibTeX  Entry
@InProceedings{mulzer_et_al:LIPIcs:2020:12215,
author = {Wolfgang Mulzer and Pavel Valtr},
title = {{Long Alternating Paths Exist}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {57:157:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771436},
ISSN = {18688969},
year = {2020},
volume = {164},
editor = {Sergio Cabello and Danny Z. Chen},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12215},
URN = {urn:nbn:de:0030drops122152},
doi = {10.4230/LIPIcs.SoCG.2020.57},
annote = {Keywords: Noncrossing path, bichromatic point sets}
}
08.06.2020
Keywords: 

Noncrossing path, bichromatic point sets 
Seminar: 

36th International Symposium on Computational Geometry (SoCG 2020)

Issue date: 

2020 
Date of publication: 

08.06.2020 