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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abellanas, M., García, A., Hurtado, F., Tejel, J.: Caminos alternantes (in Spanish). In: X Encuentros de Geometría Computacional, Sevilla, Spanish, pp. 7–12 (2003)
Abellanas, M., Garcia-Lopez, J., Hernández-Peñalver, G., Noy, M., Ramos, P.A.: Bipartite embeddings of trees in the plane. Discrete Applied Mathematics 93(2-3), 141–148 (1999)
Akiyama, J., Urrutia, J.: Simple alternating path problem. Discr. Math. 84(1), 101–103 (1990)
Chazelle, B.: Functional approach to data structures and its use in multidimensional searching. SIAM J. Comput. 17, 427–462 (1988)
Cibulka, J., Kynčl, J., Mészáros, V., Stolař, R., Valtr, P.: Hamiltonian Alternating Paths on Bicolored Double-Chains. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 181–192. Springer, Heidelberg (2009)
Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H. Freeman and Company (1979)
Kaneko, A., Kano, M., Suzuki, K.: Path coverings of two sets of points in the plane. In: Pach, J. (ed.) Towards a Theory of Geometric Graphs, vol. 342, pp. 99–111. American Mathematical Society (2004)
Kaneko, A., Kano, M., Yoshimoto, K.: Alternating Hamilton cycles with minimum number of crossings in the plane. Int. J. Comput. Geometry Appl. 10(1), 73–78 (2000)
Kano, M.: Discrete geometry on red and blue points on the plane lattice. In: Proc. of JCCGG 2009, pp. 30–33 (2009)
Katz, B., Krug, M., Rutter, I., Wolff, A.: Manhattan-Geodesic Embedding of Planar Graphs. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 207–218. Springer, Heidelberg (2010)
Kynčl, J., Pach, J., Tóth, G.: Long alternating paths in bicolored point sets. Discrete Mathematics 308(19), 4315–4321 (2008)
Merino, C., Salazar, G., Urrutia, J.: On the length of longest alternating paths for multicoloured point sets in convex position. Discrete Mathematics 306(15), 1791–1797 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Di Giacomo, E., Grilli, L., Krug, M., Liotta, G., Rutter, I. (2011). Hamiltonian Orthogeodesic Alternating Paths. In: Iliopoulos, C.S., Smyth, W.F. (eds) Combinatorial Algorithms. IWOCA 2011. Lecture Notes in Computer Science, vol 7056. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-25011-8_14
Download citation
DOI: https://doi.org/10.1007/978-3-642-25011-8_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-25010-1
Online ISBN: 978-3-642-25011-8
eBook Packages: Computer ScienceComputer Science (R0)