Bottleneck non-crossing matching in the plane

DOI10.1016/J.COMGEO.2013.10.005MaRDI QIDQ390164zbMATH OpenOpenAlexFDO

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)

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

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$.

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

Cited in

(19)

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

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)