Matching points with rectangles and squares

DOI10.1016/j.comgeo.2008.05.001zbMath1157.65018OpenAlexW2152203458MaRDI QIDQ955221

Alexander Wolff, Nikolaus Mutsanas, Sergey Bereg

Publication date: 19 November 2008

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2008.05.001

zbMATH Keywords

algorithmNP-hardnessperfect matchingmatching with geometric objectsweak and strong matching

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Computational aspects related to convexity (52B55) Graph theory (including graph drawing) in computer science (68R10) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items

On maximum-sum matchings of points, Matching points with disks with a common intersection, Strong matching of points with geometric shapes, Matching colored points with rectangles, Matching random colored points with rectangles, Fixed-orientation equilateral triangle matching of point sets

Cites Work

• Unnamed Item
• A polynomial time solution for labeling a rectilinear map
• Labeling a rectilinear map more efficiently
• Reconstructing sets of orthogonal line segments in the plane
• Toughness and Delaunay triangulations
• Boundary labeling: Models and efficient algorithms for rectangular maps
• Labeling points with given rectangles
• Point labeling with sliding labels
• Time bounds for selection
• Polynomial time algorithms for three-label point labeling.
• Labeling points with weights
• On a matching problem in the plane
• Priority Search Trees
• Planar Formulae and Their Uses
• Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains
• The Problem of Compatible Representatives
• LABELING A RECTILINEAR MAP WITH SLIDING LABELS
• Trimming of Graphs, with Application to Point Labeling
• Matching Points with Circles and Squares
• Algorithms and Computation