Bottleneck Non-Crossing Matching in the Plane

Abstract

Let $P$ be a set of $2n$ points in the plane, and let $M_{\mathrm{C}}$ (resp., $M_{\mathrm{NC}}$) denote a bottleneck matching (resp., a bottleneck non-crossing matching) of $P$. We study the problem of computing $M_{\mathrm{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)\le 2\sqrt{10}\cdot bn(M_{\mathrm{NC}})$, where $bn(M)$ is the length of a longest edge in $M$. An interesting implication of our construction is that $bn(M_{\mathrm{NC}})/bn(M_{\mathrm{C}})\le 2\sqrt{10}$.

17 pages, 13 figures

References in corpus (1)

• Compatible Geometric Matchings