Bottleneck non-crossing matching in the plane
Let P be a set of 2n  points in the plane, and let MC M C (resp., MNC M NC ) denote a bottleneck matching (resp., a bottleneck non-crossing matching) of P . We study the problem of computing MNC 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 b n ( M ) ? 2 10 ? b n ( M NC ) , where bn(M) b n ( M ) is the length of a longest edge in M . An interesting implication of our construction is that b n ( M NC ) / b n ( M C ) ? 2 10 . Finally, we show that when the points of P  are in convex position, one can compute MNC M NC in O(n3) O ( n 3 ) time, improving a result in [7].
bottleneck matching np-hardness non-crossing configuration approximation algorithms