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

algorithmmatching with geometric objectsNP-hardnessperfect matchingweak and strong matching

Mathematics Subject Classification ID

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)

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

• 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

Cited in

(15)

• 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)