Bottleneck non-crossing matching in the plane

Let P be a set of 2n   points in the plane, and let MCMC (resp., MNCMNC) denote a bottleneck matching (resp., a bottleneck non-crossing matching) of P  . We study the problem of computing MNCMNC. 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)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 MNCMNC in O(n3)O(n3) time, improving a result in [7].