Bottleneck non-crossing matching in the plane

DOI10.1016/J.COMGEO.2013.10.005zbMATH Open1281.65025arXiv1202.4146OpenAlexW2088131302MaRDI QIDQ390164FDOQ390164

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

Publication date: 22 January 2014

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

Abstract: Let $P$ be a set of $2n$ points in the plane, and let $M_{mC}$ (resp., $M_{mNC}$) denote a bottleneck matching (resp., a bottleneck non-crossing matching) of $P$. We study the problem of computing $M_{mNC}$. We first prove that the problem is NP-hard and does not admit a PTAS. Then, we present an $O(n^{1.5}lo{g}^{0.5}n)$-time algorithm that computes a non-crossing matching $M$ of $P$, such that $bn(M)le2sqrt10cdotbn(M_{mNC})$, where $bn(M)$ is the length of a longest edge in $M$. An interesting implication of our construction is that $bn(M_{mNC})/bn(M_{mC})le2sqrt10$.

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

Recommendations

• Bottleneck non-crossing matching in the plane
• Faster bottleneck non-crossing matchings of points in convex position
• Structural properties of bichromatic non-crossing matchings
• Approximating the bottleneck plane perfect matching of a point set
• A bottleneck matching problem with edge-crossing constraints

zbMATH Keywords

approximation algorithmsNP-hardnessbottleneck matchingnon-crossing configuration

Mathematics Subject Classification ID

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

Cited In (19)

• New variants of perfect non-crossing matchings
• Title not available (Why is that?)
• Monochromatic plane matchings in bicolored point set
• Connecting the dots (with minimum crossings)
• Long non-crossing configurations in the plane
• Bottleneck non-crossing matching in the plane
• Structural properties of bichromatic non-crossing matchings
• New variants of perfect non-crossing matchings
• Dynamic Euclidean bottleneck matching
• Faster bottleneck non-crossing matchings of points in convex position
• Rainbow polygons for colored point sets in the plane
• A bottleneck matching problem with edge-crossing constraints
• Matching points with things
• Approximating the bottleneck plane perfect matching of a point set
• Planar Bichromatic Bottleneck Spanning Trees
• Finding Largest Common Point Sets
• Parameterized analysis and crossing minimization problems
• Bottleneck matching in the plane
• Computing Euclidean bottleneck matchings in higher dimensions

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q390164)