78101 20191122145055.0 doi 10.1016/j.comgeo.2017.05.009 sideral 101839 ART-2018-101839 eng Claverol, Mercè On Hamiltonian alternating cycles and paths 2018 Access copy available to the general public Unrestricted 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. info:eu-repo/grantAgreement/ES/DGA/E58 info:eu-repo/grantAgreement/ES/MINECO-FEDER/MTM2014-60127-P info:eu-repo/grantAgreement/ES/MINECO-FEDER/MTM2015-63791-R info:eu-repo/semantics/openAccess by-nc-nd http://creativecommons.org/licenses/by-nc-nd/3.0/es/ 0.343 2018 MATHEMATICS, APPLIED 248 / 254 = 0.976 2018 Q4 T3 MATHEMATICS 293 / 313 = 0.936 2018 Q4 T3 0.492 2018 Computational Mathematics 2018 Q2 Computational Theory and Mathematics 2018 Q2 Geometry and Topology 2018 Q2 Control and Optimization 2018 Q2 Computer Science Applications 2018 Q2 info:eu-repo/semantics/article info:eu-repo/semantics/acceptedVersion (orcid)0000-0002-6519-1472 García, Alfredo Universidad de Zaragoza Garijo, Delia Seara, Carlos (orcid)0000-0002-9543-7170 Tejel, Javier Universidad de Zaragoza 2007 265 Universidad de Zaragoza Dpto. Métodos Estadísticos Área Estadís. Investig. Opera. 68 (2018), 146-166 Comput. geom. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 0925-7721 509412 http://zaguan.unizar.es/record/78101/files/texto_completo.pdf Postprint 83949 http://zaguan.unizar.es/record/78101/files/texto_completo.jpg?subformat=icon icon Postprint oai:zaguan.unizar.es:78101 articulos driver 2019-11-22-14:45:27 ARTICLE