BibSonomy :: publication :: Matching Points with Rectangles and Squares

Matching Points with Rectangles and Squares

Sergey Bereg, Nikolaus Mutsanas, and Alexander Wolff. Computational Geometry: Theory and Applications 42(2):93--108 (2009)

@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 = {2013-02-01T14:37:57.000+0100},
  author = {Bereg, Sergey and Mutsanas, Nikolaus and Wolff, Alexander},
  biburl = {http://www.bibsonomy.org/bibtex/238f6ffa2ad1b61756c2ef0ef26b46c2d/awolff},
  doi = {10.1016/j.comgeo.2008.05.001},
  interhash = {a416cd6ec37ee0f6ea958d937630dba4},
  intrahash = {38f6ffa2ad1b61756c2ef0ef26b46c2d},
  journal = {Computational Geometry: Theory and Applications},
  keywords = {NP-hardness approximation matching_with_geometric_objects myown perfect_matching weak_and_strong_matching},
  number = 2,
  pages = {93--108},
  pdf = {http://www1.informatik.uni-wuerzburg.de/pub/wolff/pub/bmw-mprs-09.pdf},
  succeeds = {bmw-mprs-06},
  timestamp = {2013-02-01T14:37:57.000+0100},
  title = {Matching Points with Rectangles and Squares},
  url = {http://dx.doi.org/10.1016/j.comgeo.2008.05.001},
  volume = 42,
  year = 2009
}

%0 Journal Article
%1 bmw-mprs-09
%A Bereg, Sergey
%A Mutsanas, Nikolaus
%A Wolff, Alexander
%D 2009
%J Computational Geometry: Theory and Applications
%K 
%N 2
%P 93--108
%T Matching Points with Rectangles and Squares
%R 10.1016/j.comgeo.2008.05.001
%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 $\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.

discussion

(0)

resources (URL, PDF, ...)

DOI:	10.1016/j.comgeo.2008.05.001
URL:	http://dx.doi.org/10.1016/j.comgeo.2008.05.001
internal link: ? You can use this internal link to create references to this post in your discussions. Just copy this internal link and paste it in your discussion text.
BibTeX key:	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 ın 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łfloor 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.

publication post of awolff

Matching Points with Rectangles and Squares

discussion

resources (URL, PDF, ...)

abstract