Bottleneck Non-Crossing Matching in the Plane

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

An Approximation Algorithm for the Euclidean Bottleneck Steiner Tree Problem

Given two sets of points in the plane, $P$ of $n$ terminals and $S$ of $m$ Steiner points, a Steiner tree of $P$ is a tree spanning all points of $P$ and some (or none or all) points of $S$. A Steiner tree with length of longest edge minimized is called a bottleneck Steiner tree. In this paper, we study the Euclidean bottleneck Steiner tree problem: given two sets, $P$ and $S$, and a positive integer $k le m$, find a bottleneck Steiner tree of $P$ with at most $k$ Steiner points. The problem has application in the design of wireless communication networks. We first show that the problem is NP-hard and cannot be approximated within factor $sqrt{2}$, unless $P=NP$. Then, we present a polynomial-time approximation algorithm with performance ratio 2.