Bottleneck non-crossing matching in the plane. (English) Zbl 1281.65025

Summary: Let \(P\) be a set of 2\(n\) points in the plane, and let \(M_C\) (resp., \(M_{NC}\)) denote a bottleneck matching (resp., a bottleneck non-crossing matching) of \(P\). We study the problem of computing \(M_{NC}\). We first prove that the problem is NP-hard and does not admit a PTAS. Then, we present an \(O(n^{1.5} \log^{0.5}n)\)-time algorithm that computes a non-crossing matching \(M\) of \(P\), such that \(bn(M) \leq \sqrt{10} \cdot bn(M_{NC})\), where \(bn(M)\) is the length of a longest edge in \(M\). An interesting implication of our construction is that \(bn(M_{NC})/bn(M_C) \leq 2 \sqrt{10}\). Finally, we show that when the points of \(P\) are in convex position, one can compute \(M_{NC}\) in \(O(n^3)\) time, improving a result of J. G. Carlsson and B. Armbruster [“A bottleneck matching problem with edge-crossing constraints”, Preprint (2010)].


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