On the Longest Flip Sequence to Untangle Segments in the Plane Guilherme D. da FonsecaYan GerardBastien Rivierz

2025-05-02 0 0 656.07KB 9 页 10玖币
侵权投诉
On the Longest Flip Sequence to Untangle Segments in the
Plane∗
Guilherme D. da Fonseca†Yan Gerard‡Bastien Rivier‡
March 21, 2023
Abstract
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
(
tn2
), providing a smooth transition between the convex
O
(
n2
)bound and the
general
O
(
n3
)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(n8/3).
1 Introduction
In the Euclidean Travelling Salesman Problem (TSP), we are given a set
P
of
n
points in the
plane and the goal is to produce a closed tour connecting all points of minimum total Euclidean
length. The TSP problem, both in the Euclidean and in the more general graph versions, is
one of the most studied NP-hard optimization problems, with several approximation algorithms,
as well as powerful heuristics (see for example [
2
,
13
,
17
]). Multiple PTAS are known for the
Euclidean version [
3
,
24
,
28
], in contrast to the general graph version that unlikely admits a
PTAS [
11
]. It is well known that the optimal solution for the Euclidean TSP is a simple polygon,
i.e., has no crossing segments, and in some situation a crossing-free solution is necessary [
10
].
However, most approximation algorithms (including Christofides and the PTAS), as well as a
variety of simple heuristics (nearest neighbor, greedy, and insertion, among others) may produce
solutions with pairs of crossing segments. In practice, these algorithms may be supplemented
with a local search phase, in which crossings are removed by iteratively modifying the solution.
Given a Euclidean TSP tour, a flip is an operation that removes a pair of crossing segments
and adds a new pair of segments preserving a tour (Fig. 1(a)). If we want to find a tour without
crossing segments starting from an arbitrary tour, it suffices to find a crossing, perform a flip,
and repeat until there are no crossings. It is easy to see that the process will eventually finish, as
the length of the tour can only decrease when we perform a flip. Since a flip may create several
new crossings, it is not obvious how to bound the number of flips performed until a crossing-free
solution is obtained. Let
DTSP
(
n
)denote the maximum number of flips successively performed on
a TSP tour with
n
segments. An upper bound of
DTSP
(
n
) =
O
(
n3
)is proved in [
30
], while the
∗
A version of this paper appears in Walcom’23. This work is supported by the French ANR PRC grant ADDS
(ANR-19-CE48-0005).
†Aix-Marseille Université and LIS, France. guilherme.fonseca@lis-lab.fr
‡Université Clermont Auvergne and LIMOS, France. {yan.gerard, bastien.rivier}@uca.fr
1
arXiv:2210.12036v3 [cs.CG] 17 Mar 2023
(a) (b) (c)
Figure 1: Examples of flips in a (a) TSP tour, (b) monochromatic matching, and (c) red-blue
matching.
best lower bound known is
DTSP
(
n
) = Ω(
n2
). In contrast, if the points
P
are in convex position,
then tight bounds of Θ(n2)are easy to prove.
In this paper, we show that we can consider a conceptually simpler problem of flips in
matchings (instead of Hamiltonian cycles), in order to bound the number of flips to both
problems. Next, we describe this monochromatic matching version.
Consider a set of
n
line segments in the plane defining a matching
M
on a set
P
of 2
n
points.
In this case, a flip replaces a pair of crossing segments by a pair of non-crossing ones using the
same four endpoints (Fig. 1(b)). Notice that, in contrast to the TSP version, one of two possible
pairs of non-crossing segments is added. As previously, let
DMM
(
n
)denote the maximum number
of flips successively performed on a monochromatic matching with
n
segments. In Section 2,
we show that
DMM
(
n
)
≤DTSP
(6
n
)
≤DMM
(6
n
), hence it suffices to prove asymptotic bounds for
DMM(n)in order to bound DTSP(n).
A third and last version of the problem that we consider is the red-blue matching version,
in which the set
P
is partitioned into two sets of
n
points each called red and blue, with
segments only connecting points of different colors (Fig. 1(c)). Let
DRB
(
n
)denote the analogous
maximum number of flips successively performed on a red-blue matching with
n
segments. The
red-blue matching version has been thoroughly studied [
6
,
12
]. In Section 2, we also show that
DMM
(
n
)
≤DRB
(2
n
)
≤DMM
(2
n
)and, as a consequence, asymptotic bounds for the monochromatic
matching version also extend to the red-blue matching version. We use the notation
D
(
n
)for
bounds that hold in all three versions.
For all the aforementioned versions, special cases arise when we impose some constraint on
the location of the points
P
. In the convex case,
P
is in convex position. Then it is known that,
for all three versions,
D
(
n
) = Θ(
n2
)[
6
,
8
]. This tight bound contrasts with the gap for the
general case bounds.
For all three versions in the convex case,
D
(
n
)
≤n
2
as the number of crossings decreases at
each flip. The authors have recently shown that without convexity
DRB
(
n
)
≥
1
.
5
n
2−n
4
[
12
],
which is higher than the convex bound. A major open problem conjectured in [
8
] is to determine
if the non-convex bounds are Θ(
n2
)as the convex bounds. Unfortunately, the best upper bound
known for the non-convex case remains
D
(
n
) =
O
(
n3
)[
30
] since 1981
1
, despite recent work on
this specific problem [6,8,12]. The best lower bound known is D(n) = Ω(n2)[8,12].
The argument for the convex case bound of
D
(
n
)
≤n
2
breaks down even if all but one point
are in convex position, as the number of crossings may not decrease. In Section 3, we present a
smooth transition between the convex and the non-convex cases. We show that, in all versions, if
there are
t
points anywhere and the remaining points are in convex position with a total of
n
segments, then the maximum number of flips is O(tn2).
1
While the paper considers only the TSP version, the proof of the upper bound also works for the matching
versions, as shown in [8].
2
摘要：

OntheLongestFlipSequencetoUntangleSegmentsinthePlane*GuilhermeD.daFonseca„YanGerard…BastienRivierzMarch21,2023AbstractAsetofsegmentsintheplanemayformaEuclideanTSPtouroramatching,amongothers.OptimalTSPtoursaswellasminimumweightperfectmatchingshavenocrossingsegments,butseveralheuristicsandapproximatio...

展开>> 收起<<
On the Longest Flip Sequence to Untangle Segments in the Plane Guilherme D. da FonsecaYan GerardBastien Rivierz.pdf

共9页,预览2页

还剩页未读， 继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：9 页 大小：656.07KB 格式：PDF 时间：2025-05-02

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 动力学连接体 力的合成 配电装置 高考理综 全宋诗作者索引 公务员考试
/ 9
评分 收藏
分享
立即下载
客服
关注