Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.comgeo.2008.05.001 | Comput. Geom. |
Keywords | Field | DocType |
square matching,strong rectangle,class c,set p,matching point,np-hardness,geometric matching problem,axes-aligned square,perfect strong square matching,combinatorial matching,set m,point set,weak and strong matching,matching with geometric objects,approximation,perfect matching | Discrete mathematics,Combinatorics,Optimal matching,Geometric matching,Rectangle,Natural family,Matching (graph theory),3-dimensional matching,Mathematics,Delaunay triangulation,The Intersect | Journal |
Volume | Issue | ISSN |
42 | 2 | Computational Geometry: Theory and Applications |
ISBN | Citations | PageRank |
3-540-31198-X | 5 | 0.54 |
References | Authors | |
20 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sergey Bereg | 1 | 245 | 40.81 |
| Nikolaus Mutsanas | 2 | 35 | 3.00 |
| Alexander Wolff | 3 | 222 | 22.66 |