Matching points with rectangles and squares

S. Bereg, N. Mutsanas, A. Wolff

Research output: Contribution to journalArticleAcademicpeer-review

8 Citations (Scopus)


In this paper we deal with the following natural family of geometric matching problems. Given a class of geometric objects and a set P of points in the plane, a -matching is a set such that every CM 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 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.
Original languageEnglish
Pages (from-to)93-108
JournalComputational Geometry
Issue number2
Publication statusPublished - 2009

Fingerprint Dive into the research topics of 'Matching points with rectangles and squares'. Together they form a unique fingerprint.

Cite this