Bottleneck non-crossing matching in the plane

Let P be a set of 2n points in the plane, and let ^MC (resp., ^MNC) denote a bottleneck matching (resp., a bottleneck non-crossing matching) of P. We study the problem of computing ^MNC. We first prove that the problem is NP-hard and does not admit a PTAS. Then, we present an O(^n1.5log0.5n)-time algorithm that computes a non-crossing matching M of P, such that bn(M)≤210×bn(^MNC), where bn(M) is the length of a longest edge in M. An interesting implication of our construction is that bn(^MNC)/bn(^MC)≤210. Finally, we show that when the points of P are in convex position, one can compute ^MNC in O(ⁿ³) time, improving a result in [7].