Matching points with squares

DOI10.1007/s00454-008-9099-1zbMath1191.52012OpenAlexW1990729778MaRDI QIDQ1006403

Joseph S. B. Mitchell, Jorge Urrutia, Ferran Hurtado, Mikio Kano, Esther M. Arkin, Bernardo M. Ábrego, Silvia Fernández-Merchant

Publication date: 24 March 2009

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-008-9099-1

zbMATH Keywords

discrete geometryHamiltonian pathperfect matchingDelaunay triangulations

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15) Lattices and convex bodies in (2) dimensions (aspects of discrete geometry) (52C05)

Related Items (9)

Disjoint empty disks supported by a point set ⋮ 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 ⋮ Hamiltonicity for convex shape Delaunay and Gabriel graphs ⋮ Fixed-orientation equilateral triangle matching of point sets ⋮ 10-Gabriel graphs are Hamiltonian

Cites Work

• Toughness and Delaunay triangulations
• Traveling salesman cycles are not always subgraphs of Delaunay triangulations or of minimum weight triangulations
• A non-Hamiltonian, nondegenerate Delaunay triangulation
• Guarding rectangular art galleries
• Finding Hamiltonian cycles in Delaunay triangulations is NP-complete
• A Theorem on Planar Graphs
• Towards a Theory of Geometric Graphs
• Matching Points with Circles and Squares
• SOFSEM 2006: Theory and Practice of Computer Science

This page was built for publication: Matching points with squares