000078101 001__ 78101 000078101 005__ 20191122145055.0 000078101 0247_ $$2doi$$a10.1016/j.comgeo.2017.05.009 000078101 0248_ $$2sideral$$a101839 000078101 037__ $$aART-2018-101839 000078101 041__ $$aeng 000078101 100__ $$aClaverol, Mercè 000078101 245__ $$aOn Hamiltonian alternating cycles and paths 000078101 260__ $$c2018 000078101 5060_ $$aAccess copy available to the general public$$fUnrestricted 000078101 5203_ $$aWe 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. 000078101 536__ $$9info:eu-repo/grantAgreement/ES/DGA/E58$$9info:eu-repo/grantAgreement/ES/MINECO-FEDER/MTM2014-60127-P$$9info:eu-repo/grantAgreement/ES/MINECO-FEDER/MTM2015-63791-R 000078101 540__ $$9info:eu-repo/semantics/openAccess$$aby-nc-nd$$uhttp://creativecommons.org/licenses/by-nc-nd/3.0/es/ 000078101 590__ $$a0.343$$b2018 000078101 591__ $$aMATHEMATICS, APPLIED$$b248 / 254 = 0.976$$c2018$$dQ4$$eT3 000078101 591__ $$aMATHEMATICS$$b293 / 313 = 0.936$$c2018$$dQ4$$eT3 000078101 592__ $$a0.492$$b2018 000078101 593__ $$aComputational Mathematics$$c2018$$dQ2 000078101 593__ $$aComputational Theory and Mathematics$$c2018$$dQ2 000078101 593__ $$aGeometry and Topology$$c2018$$dQ2 000078101 593__ $$aControl and Optimization$$c2018$$dQ2 000078101 593__ $$aComputer Science Applications$$c2018$$dQ2 000078101 655_4 $$ainfo:eu-repo/semantics/article$$vinfo:eu-repo/semantics/acceptedVersion 000078101 700__ $$0(orcid)0000-0002-6519-1472$$aGarcía, Alfredo$$uUniversidad de Zaragoza 000078101 700__ $$aGarijo, Delia 000078101 700__ $$aSeara, Carlos 000078101 700__ $$0(orcid)0000-0002-9543-7170$$aTejel, Javier$$uUniversidad de Zaragoza 000078101 7102_ $$12007$$2265$$aUniversidad de Zaragoza$$bDpto. Métodos Estadísticos$$cÁrea Estadís. Investig. Opera. 000078101 773__ $$g68 (2018), 146-166$$pComput. geom.$$tCOMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS$$x0925-7721 000078101 8564_ $$s509412$$uhttps://zaguan.unizar.es/record/78101/files/texto_completo.pdf$$yPostprint 000078101 8564_ $$s83949$$uhttps://zaguan.unizar.es/record/78101/files/texto_completo.jpg?subformat=icon$$xicon$$yPostprint 000078101 909CO $$ooai:zaguan.unizar.es:78101$$particulos$$pdriver 000078101 951__ $$a2019-11-22-14:45:27 000078101 980__ $$aARTICLE