Bottleneck non-crossing matching in the plane

DOI10.1016/j.comgeo.2013.10.005zbMath1281.65025arXiv1202.4146OpenAlexW2088131302MaRDI QIDQ390164

Paz Carmi, Matthew J. Katz, A. Karim Abu-Affash, Yohai Trabelsi

Publication date: 22 January 2014

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

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

zbMATH Keywords

approximation algorithmsNP-hardnessbottleneck matchingnon-crossing configuration

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (12)

New variants of perfect non-crossing matchings ⋮ Faster bottleneck non-crossing matchings of points in convex position ⋮ Parameterized analysis and crossing minimization problems ⋮ Bottleneck matching in the plane ⋮ Approximating the bottleneck plane perfect matching of a point set ⋮ Planar Bichromatic Bottleneck Spanning Trees ⋮ New variants of perfect non-crossing matchings ⋮ Structural properties of bichromatic non-crossing matchings ⋮ Rainbow polygons for colored point sets in the plane ⋮ Connecting the dots (with minimum crossings) ⋮ Monochromatic plane matchings in bicolored point set ⋮ Finding Largest Common Point Sets

This page was built for publication: Bottleneck non-crossing matching in the plane