LIPIcs.SoCG.2020.57.pdf
- Filesize: 0.6 MB
- 16 pages
Document
Long Alternating Paths Exist
Authors
Wolfgang Mulzer 
,
Pavel Valtr
-
Part of:
Volume:
36th International Symposium on Computational Geometry (SoCG 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-06-08
File
Document Identifiers
Author Details
Acknowledgements
This work was initiated at the second DACH workshop on Arrangements and Drawings which took place 21. - 25. January 2019 at Schloss St. Martin, Graz, Austria. We would like to thank the organizers and all the participants of the workshop for creating a conducive research atmosphere and for stimulating discussions. Part of this work was done on the Seventh Annual Workshop on Geometry and Graphs, Bellairs Research Institute, Holetown, Barbados, 10. - 15. March 2019. We also thank Zoltán Király for pointing out the reference [Clemens Müllner and Andrew Ryzhikov, 2019] to us.
Cite As Get BibTex
Wolfgang Mulzer and Pavel Valtr. Long Alternating Paths Exist. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 57:1-57:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SoCG.2020.57
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).
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- Non-crossing path
- bichromatic point sets
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Manuel Abellanas, Alfredo García, Ferran Hurtado, and Javier Tejel. Caminos alternantes. In X Encuentros de Geometría Computational, pages 7-12, 2003.
-
Oswin Aichholzer, Carlos Alegría, Irene Parada, Alexander Pilz, Javier Tejel, Csaba D. Tóth, Jorge Urrutia, and Birgit Vogtenhuber. Hamiltonian meander paths and cycles on bichromatic point sets. In XVIII Spanish Meeting on Computational Geometry, pages 35-38, 2019.
- Jin Akiyama and Jorge Urrutia. Simple alternating path problem. Discrete Mathematics, 84(1):101-103, 1990. URL: https://doi.org/10.1016/0012-365X(90)90276-N.
-
Peter Brass, William O. J. Moser, and János Pach. Research problems in discrete geometry. Springer, 2005.
- Josef Cibulka, Jan Kynčl, Viola Mészáros, Rudolf Stolař, and Pavel Valtr. Universal Sets for Straight-Line Embeddings of Bicolored Graphs. In János Pach, editor, Thirty Essays on Geometric Graph Theory, pages 101-119, New York, NY, 2013. Springer New York. URL: https://doi.org/10.1007/978-1-4614-0110-0_8.
-
Merce Claverol, Delia Garijo, Ferran Hurtado, Dolores Lara, and Carlos Seara. The alternating path problem revisited. In XV Spanish Meeting on Computational Geometry, pages 115-118, 2013.
-
Endre Csóka, Zoltán L. Blázsik, Zoltán Király, and Dániel Lenger. The necklace folding problem. Manuscript in preparation, 2020.
- Peter Hajnal and Viola Mészáros. Note on noncrossing path in colored convex sets. unpublished preprint, 2010. URL: http://infoscience.epfl.ch/record/175677.
-
Jan Kynčl, János Pach, and Géza Tóth. Long alternating paths in bicolored point sets. Discrete Mathematics, 308(19):4315-4321, 2008.
- Rune Lyngsø and Christian Pedersen. Protein Folding in the 2D HP Model. BRICS Report Series, 6(16), January 1999. URL: https://doi.org/10.7146/brics.v6i16.20073.
-
Viola Mészáros. Extremal problems on planar point sets. PhD thesis, University of Szeged, Bolyai Institute, 2011.
- Viola Mészáros. Separated matchings and small discrepancy colorings. In Alberto Márquez, Pedro Ramos, and Jorge Urrutia, editors, Computational Geometry - XIV Spanish Meeting on Computational Geometry, EGC 2011, Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, Alcalá de Henares, Spain, June 27-30, 2011, Revised Selected Papers, volume 7579 of Lecture Notes in Computer Science, pages 236-248. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-34191-5_23.
- Viola Mészáros. An upper bound on the size of separated matchings. Electronic Notes in Discrete Mathematics, 38:633-638, 2011. URL: https://doi.org/10.1016/j.endm.2011.10.006.
- Clemens Müllner and Andrew Ryzhikov. Palindromic subsequences in finite words. In Proc 13th Int. Conf. Language and Automata Theory and Applications (LATA), pages 460-468, 2019. URL: https://doi.org/10.1007/978-3-030-13435-8_34.