Matching points with rectangles and squares

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

Sergey Bereg, Alexander Wolff, Nikolaus Mutsanas

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

algorithm; NP-hardness; perfect matching; matching with geometric objects; weak and strong matching

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68Q25: Analysis of algorithms and problem complexity

52B55: Computational aspects related to convexity

68R10: Graph theory (including graph drawing) in computer science

65D18: Numerical aspects of computer graphics, image analysis, and computational geometry

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