Matching points with rectangles and squares

In this paper we deal with the following natural family of geometric matching problems. Given a class C of geometric objects and a set P of points in the plane, a C-matching is a set M⊆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 axes-aligned squares and rectangles.We propose an algorithm for strong rectangle matching that, given a set of n points, matches at least 2⌊n/3⌋ of them, which is worst-case optimal. If we are given a combinatorial matching of the points, we can test efficiently whether it has a realization as a (strong) square matching. The algorithm behind this test can be modified to solve an interesting new point-labeling problem. On the other hand we show that it is NP-hard to decide whether a point set has a perfect strong square matching.