Matching Points with Rectangles and Squares

In this paper we deal with the following natural family of geometric matching problems. Given a class ${\mathcal C}$ of geometric objects and a point set P, a ${\mathcal C}$-matching is a set M$\subseteq {\mathcal C}$ such that every C ∈ M contains exactly two elements of P. The matching is perfect if it covers every point, and strong if the objects do not intersect. We concentrate on matching points using axis-aligned squares and rectangles. We give algorithms for these classes and show that it is NP-hard to decide whether a point set has a perfect strong square matching. We show that one of our matching algorithms solves a family of map-labeling problems.