Given a set of red and blue points, an orthogeodesic alternating path is a path such that each edge is a geodesic orthogonal chain connecting points of different colour and no two edges cross. We consider the problem of deciding whether there exists a Hamiltonian orthogeodesic alternating path, i.e., an orthogeodesic alternating path visiting all points. We provide an O(n log2 n)-time algorithm for finding such a path if no two points are horizontally or vertically aligned. We show that the problem is NP-hard if bends must be at grid points. Nevertheless, we can approximate the maximum number of vertices of an orthogeodesic alternating path on the grid by roughly a factor of 3. Finally, we consider the problem of finding orthogeodesic alternating matchings, cycles, and trees.
Hamiltonian Orthogeodesic Alternating Paths
DI GIACOMO, Emilio;GRILLI, LUCA;LIOTTA, Giuseppe;
2011
Abstract
Given a set of red and blue points, an orthogeodesic alternating path is a path such that each edge is a geodesic orthogonal chain connecting points of different colour and no two edges cross. We consider the problem of deciding whether there exists a Hamiltonian orthogeodesic alternating path, i.e., an orthogeodesic alternating path visiting all points. We provide an O(n log2 n)-time algorithm for finding such a path if no two points are horizontally or vertically aligned. We show that the problem is NP-hard if bends must be at grid points. Nevertheless, we can approximate the maximum number of vertices of an orthogeodesic alternating path on the grid by roughly a factor of 3. Finally, we consider the problem of finding orthogeodesic alternating matchings, cycles, and trees.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
