On Hamiltonian alternating cycles and paths (Q1699287)

Assume we have \(n\) red and \(n\) blue points in the plane in general position (i.e. no three points are on the same line), \(n\geq 2\). A plane Hamiltonian alternating cycle on this point configuration is a Hamiltonian cycle whose edges are straight-line segments connecting points of different colors with no crossings. Since such cycle does not always exist, instead of being plane a relaxed condition of being 1-plane has been suggested in [the first author et al., ``The alternating path problem revisited'', in: Proceedings of the XV Spanish meeting on computational geometry, Sevilla, June 26--28, 2013. Sevilla: University of Sevilla. 115--118 (2013)], i.e. every edge is allowed to have at most one crossing. It is shown that a 1-plane Hamiltonian alternating cycle always exists and can be found in \(O(n^2)\) time and space. Moreover, when the points are in convex position, every Hamiltonian alternating cycle with minimum number of crossings is 1-plane, and such cycle can be found in \(O(n)\) time and space. Further results are obtained for paths between given endpoints on point sets in convex position. It is shown that except certain special configurations, every Hamiltonian alternating path between given endpoints with minimal number of crossings is 1-plane. This allows to find a 1-plane Hamiltonian alternating path between given endpoints with minimum number of crossings in \(O(n^2)\) time