论文标题
在最长的翻转序列上，在平面中解开片段
On the Longest Flip Sequence to Untangle Segments in the Plane
论文作者
论文摘要
飞机上的一组细分市场可能会形成欧几里得TSP之旅或匹配等。最佳的TSP游览以及最小的重量完美匹配没有交叉段，但是几种启发式方法和近似算法可能会产生带有交叉的解决方案。为了改善此类解决方案，我们可以依次应用翻转操作，该操作用非交叉段来代替一对交叉段。本文考虑了在n个段上执行的最大数字D（n）。首先，我们提出有关不同段的D（N）的减少（TSP旅行，单色匹配，红蓝色匹配和多编码）。其次，我们表明，如果除t点以外的所有除位置都处于凸位置，则d（n）= o（tn^2），在凸O（n^2）绑定与一般O（n^3）结合之间提供平滑的跃迁。最后，我们表明，如果我们不计算翻转总数，而是计算不同翻转的数量，那么立方上限将改进到O（n^{8/3}）。
A set of segments in the plane may form a Euclidean TSP tour or a matching, among others. Optimal TSP tours as well as minimum weight perfect matchings have no crossing segments, but several heuristics and approximation algorithms may produce solutions with crossings. To improve such solutions, we can successively apply a flip operation that replaces a pair of crossing segments by non-crossing ones. This paper considers the maximum number D(n) of flips performed on n segments. First, we present reductions relating D(n) for different sets of segments (TSP tours, monochromatic matchings, red-blue matchings, and multigraphs). Second, we show that if all except t points are in convex position, then D(n) = O(tn^2), providing a smooth transition between the convex O(n^2) bound and the general O(n^3) bound. Last, we show that if instead of counting the total number of flips, we only count the number of distinct flips, then the cubic upper bound improves to O(n^{8/3}).
