Matching points with squares

Bernardo M. Ábrego; Esther M. Arkin; Silvia Fernández-Merchant; Ferran Hurtado; Mikio Kano; Joseph S.B. Mitchell; Jorge Urrutia

doi:10.1007/s00454-008-9099-1

Matching points with squares

Bernardo M. Ábrego
, Esther M. Arkin
, Silvia Fernández-Merchant
, Ferran Hurtado
, Mikio Kano
, Joseph S.B. Mitchell
, Jorge Urrutia

Applied Mathematics and Statistics

California State University Northridge
Polytechnic University of Catalonia
Ibaraki University
Universidad Nacional Autónoma de México

Research output: Contribution to journal › Article › peer-review

17 Scopus citations

Abstract

Given a class C of geometric objects and a point set P, a C -matching of P is a set M={C₁,.,.,.C_k ⊂ C of elements of 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 C -matchings for point sets in the plane when 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 ₁ metric always admit a Hamiltonian path.

Original language	English
Pages (from-to)	77-95
Number of pages	19
Journal	Discrete and Computational Geometry
Volume	41
Issue number	1
DOIs	https://doi.org/10.1007/s00454-008-9099-1
State	Published - Jan 2009

Keywords

Delaunay
Discrete geometry
Hamiltonian
Matching

Access to Document

10.1007/s00454-008-9099-1

Cite this

@article{1f9ce25feaf744a9a00ab561a25029d7,

title = "Matching points with squares",

abstract = "Given a class C of geometric objects and a point set P, a C -matching of P is a set M=\{C1,.,.,.Ck ⊂ C of elements of 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 C -matchings for point sets in the plane when 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.",

keywords = "Delaunay, Discrete geometry, Hamiltonian, Matching",

author = "{\'A}brego, \{Bernardo M.\} and Arkin, \{Esther M.\} and Silvia Fern{\'a}ndez-Merchant and Ferran Hurtado and Mikio Kano and Mitchell, \{Joseph S.B.\} and Jorge Urrutia",

year = "2009",

month = jan,

doi = "10.1007/s00454-008-9099-1",

language = "English",

volume = "41",

pages = "77--95",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

number = "1",

}

TY - JOUR

T1 - Matching points with squares

AU - Ábrego, Bernardo M.

AU - Arkin, Esther M.

AU - Fernández-Merchant, Silvia

AU - Hurtado, Ferran

AU - Kano, Mikio

AU - Mitchell, Joseph S.B.

AU - Urrutia, Jorge

PY - 2009/1

Y1 - 2009/1

N2 - Given a class C of geometric objects and a point set P, a C -matching of P is a set M={C1,.,.,.Ck ⊂ C of elements of 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 C -matchings for point sets in the plane when 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.

AB - Given a class C of geometric objects and a point set P, a C -matching of P is a set M={C1,.,.,.Ck ⊂ C of elements of 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 C -matchings for point sets in the plane when 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.

KW - Delaunay

KW - Discrete geometry

KW - Hamiltonian

KW - Matching

UR - https://www.scopus.com/pages/publications/57849100621

U2 - 10.1007/s00454-008-9099-1

DO - 10.1007/s00454-008-9099-1

M3 - Article

AN - SCOPUS:57849100621

SN - 0179-5376

VL - 41

SP - 77

EP - 95

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 1

ER -

Matching points with squares

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this