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 ﬂip operation that replaces

a pair of crossing segments by non-crossing ones. This paper considers the maximum number

(

)of ﬂips performed on

segments. First, we present reductions relating

(

)for

diﬀerent sets of segments (TSP tours, monochromatic matchings, red-blue matchings, and

multigraphs). Second, we show that if all except

points are in convex position, then

(

) =

(

tn2

), providing a smooth transition between the convex

(

)bound and the

general

(

)bound. Last, we show that if instead of counting the total number of ﬂips, we

only count the number of distinct ﬂips, then the cubic upper bound improves to O(n8/3).

1 Introduction

In the Euclidean Travelling Salesman Problem (TSP), we are given a set

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 [

]). Multiple PTAS are known for the

Euclidean version [

], in contrast to the general graph version that unlikely admits a

PTAS [

]. 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 [

However, most approximation algorithms (including Christoﬁdes 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 ﬂip 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 ﬁnd a tour without

crossing segments starting from an arbitrary tour, it suﬃces to ﬁnd a crossing, perform a ﬂip,

and repeat until there are no crossings. It is easy to see that the process will eventually ﬁnish, as

the length of the tour can only decrease when we perform a ﬂip. Since a ﬂip may create several

new crossings, it is not obvious how to bound the number of ﬂips performed until a crossing-free

solution is obtained. Let

DTSP

(

)denote the maximum number of ﬂips successively performed on

a TSP tour with

segments. An upper bound of

DTSP

(

) =

(

)is proved in [

], 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

arXiv:2210.12036v3 [cs.CG] 17 Mar 2023

(a) (b) (c)

Figure 1: Examples of ﬂips in a (a) TSP tour, (b) monochromatic matching, and (c) red-blue

matching.

best lower bound known is

DTSP

(

) = Ω(

). In contrast, if the points

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 ﬂips in

matchings (instead of Hamiltonian cycles), in order to bound the number of ﬂips to both

problems. Next, we describe this monochromatic matching version.

Consider a set of

line segments in the plane deﬁning a matching

on a set

of 2

points.

In this case, a ﬂip 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

(

)denote the maximum number

of ﬂips successively performed on a monochromatic matching with

segments. In Section 2,

we show that

DMM

(

)

≤DTSP

)

≤DMM

), hence it suﬃces 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

is partitioned into two sets of

points each called red and blue, with

segments only connecting points of diﬀerent colors (Fig. 1(c)). Let

DRB

(

)denote the analogous

maximum number of ﬂips successively performed on a red-blue matching with

segments. The

red-blue matching version has been thoroughly studied [

]. In Section 2, we also show that

DMM

(

)

≤DRB

)

≤DMM

)and, as a consequence, asymptotic bounds for the monochromatic

matching version also extend to the red-blue matching version. We use the notation

(

)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

. In the convex case,

is in convex position. Then it is known that,

for all three versions,

(

) = Θ(

)[

]. This tight bound contrasts with the gap for the

general case bounds.

For all three versions in the convex case,

(

)

≤n

2

as the number of crossings decreases at

each ﬂip. The authors have recently shown that without convexity

DRB

(

)

≥

n

2−n

[

which is higher than the convex bound. A major open problem conjectured in [

] is to determine

if the non-convex bounds are Θ(

)as the convex bounds. Unfortunately, the best upper bound

known for the non-convex case remains

(

) =

(

)[

] since 1981

, despite recent work on

this speciﬁc problem [6,8,12]. The best lower bound known is D(n) = Ω(n2)[8,12].

The argument for the convex case bound of

(

)

≤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

points anywhere and the remaining points are in convex position with a total of

segments, then the maximum number of ﬂips is O(tn2).

While the paper considers only the TSP version, the proof of the upper bound also works for the matching

versions, as shown in [8].

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

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

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

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: