Faster bottleneck non-crossing matchings of points in convex position (Q2401333)

The paper deals with a set of points in a plane in convex position, i.e., the points are located at the vertices of a convex polygon. Any two points of the set can be matched using straight line segments (monochromatic points) without crossing so that each point lies at the endpoint of exactly one line segment. The authors are focused on the construction of an efficient algorithm minimizing the length of the longest straight line segment, the so-called bottleneck matching. A faster algorithm with only quadratic-time complexity (comparing to the best known algorithm of cubic time complexity) for finding a bottleneck matching for monochromatic points in convex position is presented. This algorithm can be applied in various geometric problems when matching without crossing not only points by straight line segments but also various planar objects and regions.