Artículo
On Hamiltonian alternating cycles and paths
Autor/es | Claverol, Mercé
García, Alfredo Garijo Royo, Delia Seara, Carlos Tejel, Javier |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Fecha de publicación | 2018 |
Fecha de depósito | 2020-06-19 |
Publicado en |
|
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 ... 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. |
Agencias financiadoras | Ministerio de Economía y Competitividad (MINECO). España |
Identificador del proyecto | MTM2014-60127-P |
Cita | Claverol, M., García, A., Garijo Royo, D., Seara, C. y Tejel, J. (2018). On Hamiltonian alternating cycles and paths. Computational Geometry, 68 (march 2018), 146-166. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
On Hamiltonian alternating.pdf | 531.8Kb | [PDF] | Ver/ | |