Matching points with rectangles and squares
type: Item
instance of: scholarly article
title: Matching points with rectangles and squares
zbMATH Open document ID: 1157.65018
author: Sergey Bereg
author: Nikolaus Mutsanas
author: Alexander Wolff
published in: Computational Geometry
publication date: 2008-11-19T00:00:00Z
review text: The authors deal with the following geometric matching problem: given a class \(\mathcal{C}\) of geometric objects and a set \(P\) of points in the plane, a \(\mathcal{C}\)-matching is a set \(M\subseteq{\mathcal C}\) such that every \(C\in M\) contains exactly two elements of \(P\). The matching is strong if no two elements of \(P\) intersect, and it is said to be perfect if every \(p\in P\) is contained in some \(C\in M\). The problem of matching points with geometric objects can be considered as a generalization of a graph theoretical matching where line segments are used to match pairs of points. The cases where \({\mathcal{C}}\) is made of circles or of squares are studied by \textit{B. M. Ábrego, E. M. Arkin, S. Fernández-Merchant, F. Hurtado, M. Kano, J. S. B. Mitchell} and \textit{J. Urrutia} [Lecture Notes in Computer Science 3742, 1--15 (2005; Zbl 1136.52302)], where such geometric matching problems were introduced. In the paper under review the authors consider axes-aligned rectangles and squares. An algorithm for strong rectangle matching is proposed: given a set of \(n\) points the algorithm matches at least \(2\lfloor n/3\rfloor\) of them, which is worst-case optimal. The proposed algorithm always gives matchings such that the every \(C\) in the matching contains exactly two elements of \(P\) in its boundary and no other element of \(P\) in its interior. In the rectangle case the two points are vertices of the rectangle, but this can not happen in the square case. If a combinatorial matching of the points is given, the authors propose a test to decide whether it has a realization as a strong square matching. This problem is strongly related to map-labelling problems. Finally, it is shown that it is \(NP\)-hard to decide whether a given point set admits a perfect strong square matching.
reviewed by: Juan Monterde
Mathematics Subject Classification ID: 65D18
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 52B55
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5368798
zbMATH Keywords: matching with geometric objects
zbMATH Keywords: weak and strong matching
zbMATH Keywords: perfect matching
zbMATH Keywords: NP-hardness
zbMATH Keywords: algorithm
MaRDI profile type: Publication
full work available at URL: j.comgeo.2008.05.001
OpenAlex ID: W2152203458
cites work: Matching Points with Circles and Squares
cites work: Time bounds for selection
cites work: Boundary labeling: Models and efficient algorithms for rectangular maps
cites work: Toughness and Delaunay triangulations
cites work: Polynomial time algorithms for three-label point labeling.
cites work: On a matching problem in the plane
cites work: Trimming of Graphs, with Application to Point Labeling
cites work: Algorithms and Computation
cites work: Labeling points with given rectangles
cites work: The Problem of Compatible Representatives
cites work: LABELING A RECTILINEAR MAP WITH SLIDING LABELS
cites work: Planar Formulae and Their Uses
cites work: Priority Search Trees
cites work: Labeling points with weights
cites work: A polynomial time solution for labeling a rectilinear map
cites work: Q2753953
cites work: Reconstructing sets of orthogonal line segments in the plane
cites work: Labeling a rectilinear map more efficiently
cites work: Point labeling with sliding labels
cites work: Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains
DOI: 10.1016/J.COMGEO.2008.05.001
description: scientific article; zbMATH DE number 5368798