Abstract
Given a class \(\mathcal{C}\) of geometric objects and a point set P, a \(\mathcal{C}\) -matching of P is a set \(M=\{C_{1},\dots,C_{k}\}\subseteq \mathcal{C}\) of elements of \(\mathcal{C}\) such that each C i contains exactly two elements of P and each element of P lies in at most one C i . If all of the elements of P belong to some C i , M is called a perfect matching. If, in addition, all of the elements of M are pairwise disjoint, we say that this matching M is strong. In this paper we study the existence and characteristics of \(\mathcal{C}\) -matchings for point sets in the plane when \(\mathcal{C}\) is the set of isothetic squares in the plane. A consequence of our results is a proof that the Delaunay triangulations for the L ∞ metric and the L 1 metric always admit a Hamiltonian path.
Article PDF
Similar content being viewed by others
References
Ábrego, B.M., Arkin, E., Fernández-Merchant, S., Hurtado, F., Kano, M., Mitchell, J.S.B., Urrutia, J.: Matching points with circles and squares. In: Proc. Japan Conference on Discrete and Computational Geometry 2004. Lecture Notes in Computer Science, vol. 3742, pp. 1–15. Springer, Berlin (2005)
Bereg, S., Mutsanas, N., Wolff, A.: Matching points with rectangles and squares. In: Proc. 32nd Int. Conf. on Current Trends in Theory and Practice of Computer Science (SOFSEM’06). Lecture Notes in Computer Science, vol. 3831, pp. 177–186. Springer, Berlin (2006)
Czyzowicz, J., Rivera-Campo, E., Urrutia, J., Zaks, J.: Guarding rectangular art galleries. Discrete Math. 50, 149–157 (1994)
Dillencourt, M.B.: A non-Hamiltonian, nondegenerate Delaunay triangulation. Inf. Process. Lett. 25(3), 149–151 (1987)
Dillencourt, M.B.: Toughness and Delaunay triangulations. Discrete Comput. Geom. 5(6), 575–601 (1990). Preliminary version in Proc. of the 3rd Ann. Symposium on Computational Geometry, Waterloo, pp. 186–194 (1987)
Dillencourt, M.B.: Traveling salesman cycles are not always subgraphs of Delaunay triangulations or of minimum weight triangulations. Inf. Process. Lett. 24(5), 339–342 (1987)
Dillencourt, M.B.: Finding Hamiltonian cycles in Delaunay triangulations is NP-Complete. Discrete Appl. Math. 64(3), 207–217 (1996)
Liotta, G.: Proximity drawings. In: R. Tamassia (ed.) Handbook of Graph Drawing and Visualization. Chapman & Hall/CRC Press (2009, in press). ISBN 1584884126
Liotta, G., Lubiw, A., Meijer, H., Whitesides, S.H.: The rectangle of influence drawability problem. Discrete Comput. Geom. 5(6), 575–601 (1990)
Pach, J. (ed.): Towards a Theory of Geometric Graphs. Contemp. Math. Series, vol. 342. Am. Math. Soc., Providence (2004)
Tutte, W.T.: A theorem on planar graphs. Trans. Am. Math. Soc. 82, 99–116 (1956)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ábrego, B.M., Arkin, E.M., Fernández-Merchant, S. et al. Matching Points with Squares. Discrete Comput Geom 41, 77–95 (2009). https://doi.org/10.1007/s00454-008-9099-1
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-008-9099-1