On Hamiltonian alternating cycles and paths

Claverol, Mercè ; García, Alfredo (Universidad de Zaragoza) ; Garijo, Delia ; Seara, Carlos ; Tejel, Javier (Universidad de Zaragoza)

Resumen: We undertake a study on computing Hamiltonian alternating cycles and paths on bicolored point sets. This has been an intensively studied problem, not always with a solution, when the paths and cycles are also required to be plane. In this paper, we relax the constraint on the cycles and paths from being plane to being 1-plane, and deal with the same type of questions as those for the plane case, obtaining a remarkable variety of results. For point sets in general position, our main result is that it is always possible to obtain a 1-plane Hamiltonian alternating cycle. When the point set is in convex position, we prove that every Hamiltonian alternating cycle with minimum number of crossings is 1-plane, and provide O(n) and O(n2) time algorithms for computing, respectively, Hamiltonian alternating cycles and paths with minimum number of crossings.

Idioma: Inglés

DOI: 10.1016/j.comgeo.2017.05.009

Año: 2018

Publicado en: COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 68 (2018), 146-166
ISSN: 0925-7721

Factor impacto JCR: 0.343 (2018)

Categ. JCR: MATHEMATICS, APPLIED rank: 248 / 254 = 0.976 (2018) - Q4 - T3
Categ. JCR: MATHEMATICS rank: 293 / 313 = 0.936 (2018) - Q4 - T3

Factor impacto SCIMAGO: 0.492 - Computational Mathematics (Q2) - Computational Theory and Mathematics (Q2) - Geometry and Topology (Q2) - Control and Optimization (Q2) - Computer Science Applications (Q2)

Financiación: info:eu-repo/grantAgreement/ES/DGA/E58
Financiación: info:eu-repo/grantAgreement/ES/MINECO-FEDER/MTM2014-60127-P
Financiación: info:eu-repo/grantAgreement/ES/MINECO-FEDER/MTM2015-63791-R

Tipo y forma: Artículo (PostPrint)

Área (Departamento): Área Estadís. Investig. Opera. (Dpto. Métodos Estadísticos)