论文标题
完美的非交战的新变体
New variants of Perfect Non-crossing Matchings
论文作者
论文摘要
鉴于飞机上的一组点，我们有兴趣将它们与直线段匹配。我们专注于完美（所有点均匹配）非交叉（没有两个边缘相交）匹配。除了众所周知的Minmax变化（最小边的长度最小化）外，我们通过研究Maxmin，Minmin和Maxmax等不同的优化变体来扩展工作。我们考虑这些问题的单色和双重版本，并且通过采用多种技术，我们为各种输入点配置提供了有效的算法。
Given a set of points in the plane, we are interested in matching them with straight line segments. We focus on perfect (all points are matched) non-crossing (no two edges intersect) matchings. Apart from the well known MinMax variation, where the length of the longest edge is minimized, we extend work by looking into different optimization variants such as MaxMin, MinMin, and MaxMax. We consider both the monochromatic and bichromatic versions of these problems and by employing diverse techniques we provide efficient algorithms for various input point configurations.
