Matching points with rectangles and squares
Computational aspects related to convexity (52B55) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35)
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.
- A polynomial time solution for labeling a rectilinear map
- Algorithms and Computation
- Boundary labeling: Models and efficient algorithms for rectangular maps
- scientific article; zbMATH DE number 1670674 (Why is no real title available?)
- Labeling a rectilinear map more efficiently
- LABELING A RECTILINEAR MAP WITH SLIDING LABELS
- Labeling points with given rectangles
- Labeling points with weights
- Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains
- Matching Points with Circles and Squares
- On a matching problem in the plane
- Planar Formulae and Their Uses
- Point labeling with sliding labels
- Polynomial time algorithms for three-label point labeling.
- Priority Search Trees
- Reconstructing sets of orthogonal line segments in the plane
- The Problem of Compatible Representatives
- Time bounds for selection
- Toughness and Delaunay triangulations
- Trimming of graphs, with application to point labeling
- Matching points with squares
- Labeling points with given rectangles
- Strong matching of points with geometric shapes
- Matching fixed rectangles in 2-dimension
- Matching points with disks with a common intersection
- On maximum-sum matchings of points
- Matching colored points with rectangles
- scientific article; zbMATH DE number 2200862 (Why is no real title available?)
- Matching Points with Circles and Squares
- Matching random colored points with rectangles
- SOFSEM 2006: Theory and Practice of Computer Science
- Matching random colored points with rectangles
- Applications of a numbering scheme for polygonal obstacles in the plane
- Fixed-orientation equilateral triangle matching of point sets
- Finding squares and rectangles in sets of points
This page was built for publication: Matching points with rectangles and squares
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q955221)
