License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2020.57
URN: urn:nbn:de:0030-drops-122152
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12215/
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 non-crossing 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 non-crossing alternating path of length at least (1 + ε)n. The result is obtained through a slightly stronger statement: there always exists a non-crossing 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:1--57:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Sergio Cabello and Danny Z. Chen},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12215},
URN = {urn:nbn:de:0030-drops-122152},
doi = {10.4230/LIPIcs.SoCG.2020.57},
annote = {Keywords: Non-crossing path, bichromatic point sets}
}
|
Keywords: |
|
Non-crossing path, bichromatic point sets |
|
Collection: |
|
36th International Symposium on Computational Geometry (SoCG 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
08.06.2020 |
