@inproceedings{aed01bf3378c4f33b0d08324131d093b,
title = "Matching points with rectangles and squares",
abstract = "In this paper we deal with the following natural family of geometric matching problems. Given a class C of geometric objects and a point set P, 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 axis-aligned squares and rectangles. We give algorithms for these classes and show that it is NP-hard to decide whether a point set has a perfect strong square matching. We show that one of our matching algorithms solves a family of map-labeling problems.",
author = "S. Bereg and N. Mutsanas and A. Wolff",
year = "2006",
doi = "10.1007/11611257_15",
language = "English",
isbn = "3-540-31198-X",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "177--186",
editor = "J. Wiedermann and G. Tel and J. Pokorny and M. Bielikov{\'a} and J. Stuller",
booktitle = "SOFSEM 2006 : Theory and Practice of Computer Science",
address = "Germany",
}