Approximating the bottleneck plane perfect matching of a point set

DOI10.1016/j.comgeo.2015.06.005zbMath1332.65029arXiv1311.5197OpenAlexW1710148940MaRDI QIDQ904112

A. Karim Abu-Affash, Paz Carmi, Anil Maheshwari, Ahmad Biniaz, Michiel H. M. Smid

Publication date: 15 January 2016

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

Full work available at URL: https://arxiv.org/abs/1311.5197

zbMATH Keywords

approximation algorithmNP-hardgeometric graphunit disk graphbottleneck matchingplane matching

Mathematics Subject Classification ID

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

Related Items (9)

Faster bottleneck non-crossing matchings of points in convex position ⋮ Parameterized analysis and crossing minimization problems ⋮ Geometric planar networks on bichromatic collinear points ⋮ Crossing-Free Perfect Matchings in Wheel Point Sets ⋮ Planar Bichromatic Bottleneck Spanning Trees ⋮ Plane and planarity thresholds for random geometric graphs ⋮ Connecting the dots (with minimum crossings) ⋮ Euclidean bottleneck bounded-degree spanning tree ratios ⋮ Monochromatic plane matchings in bicolored point set

Cites Work

• Unnamed Item
• Unnamed Item
• Bottleneck non-crossing matching in the plane
• Non-crossing matchings of points with geometric objects
• Solving the Euclidean bottleneck matching problem by \(k\)-relative neighborhood graphs
• Transitions in geometric minimum spanning trees
• Computing Euclidean bottleneck matchings in higher dimensions
• A Bottleneck Matching Problem with Edge-Crossing Constraints
• Geometry Helps in Matching
• Paths, Trees, and Flowers
• Geometry helps in bottleneck matching and related problems

This page was built for publication: Approximating the bottleneck plane perfect matching of a point set