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.
%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
}