Matching points with rectangles and squares (Q955221)

The authors deal with the following geometric matching problem: given a class \(\mathcal{C}\) of geometric objects and a set \(P\) of points in the plane, a \(\mathcal{C}\)-matching is a set \(M\subseteq{\mathcal C}\) such that every \(C\in M\) contains exactly two elements of \(P\). The matching is strong if no two elements of \(P\) intersect, and it is said to be perfect if every \(p\in P\) is contained in some \(C\in M\). The problem of matching points with geometric objects can be considered as a generalization of a graph theoretical matching where line segments are used to match pairs of points. The cases where \({\mathcal{C}}\) is made of circles or of squares are studied by \textit{B. M. Ábrego, E. M. Arkin, S. Fernández-Merchant, F. Hurtado, M. Kano, J. S. B. Mitchell} and \textit{J. Urrutia} [Lecture Notes in Computer Science 3742, 1--15 (2005; Zbl 1136.52302)], where such geometric matching problems were introduced. In the paper under review the authors consider axes-aligned rectangles and squares. An algorithm for strong rectangle matching is proposed: given a set of \(n\) points the algorithm matches at least \(2\lfloor n/3\rfloor\) of them, which is worst-case optimal. The proposed algorithm always gives matchings such that the every \(C\) in the matching contains exactly two elements of \(P\) in its boundary and no other element of \(P\) in its interior. In the rectangle case the two points are vertices of the rectangle, but this can not happen in the square case. If a combinatorial matching of the points is given, the authors propose a test to decide whether it has a realization as a strong square matching. This problem is strongly related to map-labelling problems. Finally, it is shown that it is \(NP\)-hard to decide whether a given point set admits a perfect strong square matching.