Matching points with rectangles and squares

DOI10.1016/J.COMGEO.2008.05.001MaRDI QIDQ955221zbMATH OpenOpenAlexFDO

Authors Sergey Bereg, Nikolaus Mutsanas, Alexander Wolff

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) Graph theory (including graph drawing) in computer science (68R10) Computational aspects related to convexity (52B55) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Recommendations

• SOFSEM 2006: Theory and Practice of Computer Science
• Matching Points with Circles and Squares
• Matching colored points with rectangles
• Matching points with squares
• Strong matching of points with geometric shapes

Cites work

• scientific article; zbMATH DE number 1670674 (Why is no real title available?)
• A polynomial time solution for labeling a rectilinear map
• Algorithms and Computation
• Boundary labeling: Models and efficient algorithms for rectangular maps
• LABELING A RECTILINEAR MAP WITH SLIDING LABELS
• Labeling a rectilinear map more efficiently
• 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

Cited in

(13)

• Matching Points with Circles and Squares
• Applications of a numbering scheme for polygonal obstacles in the plane
• Matching fixed rectangles in 2-dimension
• SOFSEM 2006: Theory and Practice of Computer Science
• scientific article; zbMATH DE number 2200862 (Why is no real title available?)
• Fixed-orientation equilateral triangle matching of point sets
• Strong matching of points with geometric shapes
• Matching points with squares
• Matching points with disks with a common intersection
• On maximum-sum matchings of points
• Matching random colored points with rectangles
• Labeling points with given rectangles
• Matching colored points with rectangles

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)