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. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1007/s00454-008-9099-1 | Discrete & Computational Geometry |
Keywords | Field | DocType |
Discrete geometry,Matching,Delaunay,Hamiltonian | Discrete geometry,Discrete mathematics,Topology,Combinatorics,Disjoint sets,Hamiltonian (quantum mechanics),Hamiltonian path,Matching (graph theory),Mathematics,Delaunay triangulation | Journal |
Volume | Issue | ISSN |
41 | 1 | 0179-5376 |
Citations | PageRank | References |
6 | 0.55 | 9 |
Authors | ||
7 |
Name | Order | Citations | PageRank |
---|---|---|---|
Bernardo M. Ábrego | 1 | 95 | 18.90 |
Esther M. Arkin | 2 | 1207 | 158.07 |
Silvia Fernández-Merchant | 3 | 96 | 17.56 |
Ferran Hurtado | 4 | 744 | 86.37 |
Mikio Kano | 5 | 548 | 99.79 |
Joseph S.B. Mitchell | 6 | 4329 | 428.84 |
Jorge Urrutia | 7 | 1064 | 134.74 |