Matching Points with Squares
Given a class C of geometric objects and a point set P, a C-matching of P is a set M = {C(1),..., C(k)} subset of 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(infinity) metric and the L(1) metric always admit a Hamiltonian path.
matching delaunay hamiltonian discrete geometry