2026-07-26T03:03:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12215 2024-03-06T10:49:43Z ddc:004 open_access

Long Alternating Paths Exist Mulzer, Wolfgang Valtr, Pavel Non-crossing path bichromatic point sets 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Wolfgang Mulzer and Pavel Valtr 2020 Is Part Of LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2020.57 urn:nbn:de:0030-drops-122152 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.57 eng https://creativecommons.org/licenses/by/3.0/legalcode