%0 Journal Article %1 bmw-mprs-09 %A Bereg, Sergey %A Mutsanas, Nikolaus %A Wolff, Alexander %D 2009 %J #CGTA# %K weakandstrongmatching approximation perfectmatching NP-hardness Matchingwithgeometricobjects %N 2 %P 93--108 %R 10.1016/j.comgeo.2008.05.001 %T Matching Points with Rectangles and Squares %U http://dx.doi.org/10.1016/j.comgeo.2008.05.001 %V 42 %X 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 $2n/3 \rfloor$ 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.

@article{bmw-mprs-09, abstract = {In this paper we deal with the following natural family of geometric matching problems. Given a class $\cal C$ of geometric objects and a set $P$ of points in the plane, a $\cal C$-matching is a set $M \subseteq \cal C$ such that every $C \in M$ contains exactly two elements of $P$. The matching is \emph{perfect} if it covers every point, and \emph{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\lfloor n/3 \rfloor$ 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.}, added-at = {2010-04-13T09:41:23.000+0200}, author = {Bereg, Sergey and Mutsanas, Nikolaus and Wolff, Alexander}, biburl = {https://www.bibsonomy.org/bibtex/2edaef3610c7eeb725c0fc32e6d709dee/fink}, doi = {10.1016/j.comgeo.2008.05.001}, interhash = {a416cd6ec37ee0f6ea958d937630dba4}, intrahash = {edaef3610c7eeb725c0fc32e6d709dee}, journal = {#CGTA#}, keywords = {weakandstrongmatching approximation perfectmatching NP-hardness Matchingwithgeometricobjects}, number = 2, pages = {93--108}, pdf = {#AWPUBURL#bmw-mprs-09.pdf}, succeeds = {bmw-mprs-06}, timestamp = {2010-04-13T09:41:23.000+0200}, title = {Matching Points with Rectangles and Squares}, url = {http://dx.doi.org/10.1016/j.comgeo.2008.05.001}, volume = 42, year = 2009 }