# Identifying Riemannian singularities with regular non-Riemannian geometry

Kevin Morand<EMAIL_ADDRESS>Jeong-Hyuck Park<EMAIL_ADDRESS>Department of Physics, Sogang University, 35 Baekbeom-ro, Mapo-gu, Seoul
04107, Korea  Miok Park<EMAIL_ADDRESS>Center for Theoretical Physics
of the Universe, Institute for Basic Science, Daejeon 34126, Korea  Valid from
August 2021. School of Physics, Korea Institute for Advanced Study, Seoul
02455, Korea

###### Abstract

Admitting non-Riemannian geometries, Double Field Theory extends the notion of
spacetime beyond the Riemannian paradigm. We identify a class of singular
spacetimes known in General Relativity with regular non-Riemannian geometries.
The former divergences merely correspond to coordinate singularities of the
generalised metric for the latter. Computed in string frame, they feature an
impenetrable non-Riemannian sphere outside of which geodesics are complete
with no singular deviation. Approaching the non-Riemannian points, particles
freeze and strings become (anti-)chiral.

##  I Introduction

Spacetime singularities urge General Relativity (GR) to evolve. If not
in—still elusive—quantum gravity, the singularities in any Riemannian metric-
based classical theories of gravity have several layers: i) curable,
coordinate singularity of the metric, ii) genuine, curvature singularity, and
iii) geodesic incompleteness, as featured prominently in Penrose theorem
Penrose:1964wq . However, on the one hand, ii) does not necessarily imply iii)
(see e.g. Olmo:2015bya  for a recent example) and, on the other hand, one
encounters an intrinsic ambiguity in choosing a frame Faraoni:1998qx ;
Faraoni:2006fx  when applying these notions to scalar-tensor theories, e.g.
Horndeski:1974wa , since Weyl transformations simply do not leave curvatures
and geodesics invariant.

From a string theory perspective, the Riemannian metric $g_{\mu\nu}$ is only a
fraction of the massless sector of closed strings which should further contain
a skew-symmetric $B$-field and a scalar dilaton $\phi$. The theory implies a
crucial symmetry, $\mathbf{O}(D,D)$ with spacetime dimension $D$, which
transforms the trio $\\{g,B,\phi\\}$ into one another Buscher:1987sk ;
Buscher:1987qj . It calls for an $\mathbf{O}(D,D)$ singlet,
$e^{-2d}=\sqrt{-g}e^{-2\phi}$, and an $\mathbf{O}(D,D)$ tensor,

${\cal
H}_{AB}=\scalebox{0.9}{\\!$\left(\\!\begin{array}[]{cc}g^{-1}&-g^{-1}B\\\
Bg^{-1}&g-Bg^{-1}B\end{array}\\!\right)\\!=\\!\left(\\!\\!\begin{array}[]{cc}1&0\\\
B&1\end{array}\\!\right)\\!\\!\left(\\!\\!\begin{array}[]{cc}g^{-1}&\\!0\\\
0&\\!g\end{array}\\!\\!\right)\\!\\!\left(\\!\\!\begin{array}[]{cc}1&-B\\\
0&1\end{array}\\!\\!\right)$}\,,$ (1)

which served as generalised metric in the $\mathbf{O}(D,D)$ manifest
formulations of both string worldsheet actions Giveon:1988tt ; Duff:1989tf ;
Tseytlin:1990nb ; Tseytlin:1990va ; Rocek:1991ps ; Giveon:1991jj ; Hull:2004in
; Hull:2006qs ; Hull:2006va  and target spacetime effective descriptions
currently called Double Field Theory (DFT) Siegel:1993xq ; Siegel:1993th ;
Hull:2009mi ; Hull:2009zb ; Hohm:2010jy ; Hohm:2010pp . By taking not
$\\{g,B,\phi\\}$ but the $\mathbf{O}(D,D)$ multiplets themselves as the
fundamental variables, DFT opens a new avenue beyond the Riemannian paradigm
Lee:2013hma ; Morand:2017fnv ; Cho:2019ofr ; Park:2020ixf . In this approach,
$e^{-2d}$ is an elementary scalar density with a unit diffeomorphic weight,
and ${\cal H}_{AB}$ satisfies its own defining properties,

$\begin{array}[]{ll}{\cal H}_{AB}={\cal H}_{BA}\,,&\qquad{\cal
H}_{A}{}^{C}{\cal H}_{B}{}^{D}{\cal J}_{CD}={\cal J}_{AB}\,.\end{array}$ (2)

Here ${\cal
J}_{AB}{\,=\\!\scalebox{0.6}{$\mathbf{\left(\begin{array}[]{cc}\mathbf{0}&\mathbf{1}\\\
\mathbf{1}&\mathbf{0}\end{array}\right)}$}}$ is the $\mathbf{O}(D,D)$
invariant metric which, with its inverse, lowers and raises the
$\mathbf{O}(D,D)$ indices, $A,B=1,2,\ldots,2D$. Seen as a square matrix,
${\cal H}_{A}{}^{B}$ squares to identity hence is invertible with
$\left|\det{\cal H}\right|=1$.

Remarkably, DFT can be formulated in terms of any generalised metric that
satisfies the defining relations (2), and may have evolved to an alternative
‘pure gravity’ in the sense that both $d$ and ${\cal H}_{AB}$, i.e. the whole
closed string massless sector, are taken as the fundamental, gravitational
fields. It is by now fully equipped with its own Christoffel symbols
$\Gamma_{ABC}$, scalar/Ricci/Einstein curvatures Jeon:2011cn ; Park:2015bza ,
and Einstein equations coupled to extra ‘matter’: $G_{AB}=8\pi G\,T_{AB}$
Angus:2018mep . This single expression unifies the equations of motion of the
fundamental variables $\\{d,{\cal H}_{AB}\\}$. Besides, as solutions to
condition (2), all possible classical geometries which DFT is capable of
describing have been classified by two non-negative integers, $(n,{\bar{n}})$
Morand:2017fnv . Only the type $(0,0)$ is Riemannian, amounting to the well-
known parametrisation (1), while others are non-Riemannian in nature: the
upper left ${D\times D}$ block of the generalised metric is degenerate with
‘nullity’, i.e. dimension of the kernel, ${n+{\bar{n}}}$, and thus does not
yield an invertible Riemannian metric. For a non-Riemannian geometry to be a
consistent string background at the quantum level, it turns out necessary to
put ${n={\bar{n}}}$ in the usual critical dimensions, ${D=10}$ or $26$
Park:2020ixf . Non-relativistic string Gomis:2000bd ; Danielsson:2000gi ;
Gomis:2005pg , or torsional/stringy Newton–Cartan gravities of recent interest
Christensen:2013lma ; Hartong:2015zia ; Harmark:2017rpg ; Harmark:2018cdl ;
Bergshoeff:2018yvt ; Bergshoeff:2019pij ; Harmark:2019upf ; Bergshoeff:2021bmc
are of the type $(1,1)$ Ko:2015rha ; Park:2016sbw ; Berman:2019izh ;
Blair:2019qwi ; Cho:2019ofr ; Gallegos:2020egk ; Blair:2020gng ; Blair:2021ycc
. The condition ${n={\bar{n}}}$ further makes the non-Riemannian geometry
compatible with type II supersymmetric DFT and superstring Jeon:2012hp ;
Park:2016sbw  (c.f. Coimbra:2011nw ; Hatsuda:2015cia ): for spin group
$\mathbf{Spin}(t,s){\times\mathbf{Spin}(s,t)}$ with ${t+s=10}$, the allowed
range of ${n={\bar{n}}}$ is from zero to $\min(t,s)$ Morand:2017fnv .

Formally, DFT employs a doubled coordinate system,
$x^{A}=(\tilde{x}_{\mu},x^{\nu})$, and subsequently unifies diffeomorphisms
and $B$-field gauge symmetry into ‘doubled’ diffeomorphisms. Yet, the geometry
is not truly doubled: half of the coordinate dependency should be turned off
e.g. by setting
${\scalebox{1.1}{${\frac{\partial~{}}{\partial\tilde{x}_{\mu}}}$}\equiv 0}$,
up to $\mathbf{O}(D,D)$ rotations. This may suggest that half of the doubled
coordinates are actually gauged Park:2013mpa . By gauging e.g.
$\tilde{x}_{\mu}$ explicitly as ${\rm D}x^{A}=\big{(}{\rm
d}\tilde{x}_{\mu}-A_{\mu},{\rm d}x^{\nu}\big{)}$, it is possible to define an
$\mathbf{O}(D,D)$-symmetric proper length Park:2017snt  by means of the
corresponding pull-back of the generalised metric ${\rm D}x^{A}{\rm
D}x^{B}{\cal H}_{AB}$, and to further construct ‘doubled-yet-gauged’ actions
for particles Ko:2016dxa ; Basile:2019pic  and strings Lee:2013hma ;
Park:2016sbw . When the generalised metric is $(0,0)$ Riemannian, all the
components of the auxiliary gauge connection $A_{\mu}$ appear quadratically in
the actions. After integrating them out, one recovers the conventional
particle and string actions. On the other hand, when the background is non-
Riemannian, ${n+{\bar{n}}}$ components come out linearly to play the role of
Lagrange multipliers. Consequently, the particle is frozen with identically
vanishing proper velocities over the non-Riemannian
$({n+{\bar{n}}})$-dimensions. Further, the string becomes chiral over the
$n$-directions and anti-chiral over the ${\bar{n}}$-directions Morand:2017fnv
, as happens in the $(1,1)$ non-relativistic string case Gomis:2000bd . This
also implies that, at the classical level, chiral strings get frozen too
Park:2020ixf .

From the Riemannian perspective, all the non-Riemannian backgrounds are
singular geometries, as the would-be Riemannian metric diverges.
Contradistinctly, they are well-behaved regular geometries in the doubled
framework. This motivates us to revisit known singular Riemannian geometries
and examine their non-Riemannian regularity, c.f. earlier related discussions
in Malek:2013sp ; Berman:2014hna ; Ko:2016dxa ; Blair:2016xnn . In this
Letter, we report that a class of curvature singularities in GR are regular
non-Riemannian geometries of DFT. They are at worst coordinate singularities
of DFT. Moreover, we show through examples that the ordinary (undoubled)
geodesics defined in their string frame—which descend from
$\mathbf{O}(D,D)$-symmetric (doubled) geodesics—are complete and that
physically measurable tidal forces do not diverge, in spite of Riemannian
curvature singularities. This last statement, although motivated by the DFT
perspective, holds independently within the conventional GR setup.

##  II Main Idea & Results

The Riemann-wise singular geometries of our interest assume the following
generic form, with $x^{\mu}=(t,y,x^{i})$,

$\begin{array}[]{cll}{{\rm d}}s^{2}&\\!=\\!&\frac{1}{F}\left(-{{\rm
d}}t^{2}+{{\rm d}}y^{2}\right)+G_{ij}{{\rm d}}x^{i}{{\rm d}}x^{j}\,,\\\
B_{(2)}&\\!=\\!&\pm\frac{1}{F}\,{{\rm d}}t\wedge{{\rm
d}}y+\frac{1}{2}\,\beta_{\mu\nu}{{\rm d}}x^{\mu}\wedge{{\rm d}}x^{\nu}\,,\\\
e^{-2\phi}&\\!=\\!&F\Psi\,.\vspace{-5pt}\end{array}$ (3)

Our non-exhaustive list of examples includes A. ${D=2}$ black hole by Witten
Witten:1991yr , B. ${D=4}$ spherical solution by Burgess et al. Burgess:1994kq
, and C. ${D=10}$ black $5$-brane by Horowitz and Strominger Horowitz:1991cd .
All of them feature curvature singularities where $F$ vanishes, while
$G_{ij},\beta_{\mu\nu},\Psi$ remain harmlessly regular. Substituting (3) into
(1) yields the crucial observation (c.f. Lee:2013hma ; Blair:2015eba ;
Berman:2019izh ; Blair:2019qwi  for earlier examples) that the coordinate
singularity is absent in the $\mathbf{O}(D,D)$ fundamental variables: no
negative power of $F$ appears,

$\begin{array}[]{ll}e^{-2d}=\Psi\sqrt{G}\,,&\qquad{\cal
H}=\scalebox{0.8}{$\left(\\!\\!\begin{array}[]{cc}\mathbf{1}&\mathbf{0}\\\
\,\bf{\beta}&\mathbf{1}\end{array}\\!\right)$}\mathring{{\cal
H}}\scalebox{0.8}{$\left(\\!\\!\begin{array}[]{cc}\mathbf{1}&\bf{-\beta}\\\
\mathbf{0}&\mathbf{1}\end{array}\\!\\!\right)$}\,,\end{array}\vspace{-9pt}$
(4)

where, with Pauli matrices,

$\mathring{{\cal
H}}_{AB}=\scalebox{0.8}{$\left(\begin{array}[]{cccc}-F\sigma_{3}&0&~{}~{}\pm\sigma_{1}{}{}&~{}~{}0{}{}\\\
0&G^{-1}&0&0\\\ \pm\sigma_{1}&0&0&0\\\ 0&0&0&G\end{array}\right)$}\,.$ (5)

Clearly, at the points where ${F=0}$, the DFT geometry is non-Riemannian,
specifically of type $(1,1)$, as expected from the underlying Minkowskian spin
group signature.

We now revisit the three aforementioned layers of singularity from the
‘doubled’ perspective.

###  i)) Removing the coordinate singularity from generalised metric through
doubled diffeomorphisms.

The singular term in $B_{(2)}$ is crucial in regularising ${\cal H}$. In fact,
in the examples below, this term being pure gauge would not be present when
writing the solutions in their simplest form. We shall nevertheless introduce
such a singular pure gauge term in order to match the privileged doubled
coordinate system (3). Namely, through doubled diffeomorphisms, one can
eliminate what should be construed as a coordinate singularity of the
generalised metric.

###  ii)) All the $\mathbf{O}(D,D)$-symmetric curvatures are regular.

Once the DFT fundamental variables $\\{{\cal H}_{AB},e^{-2d}\\}$ are made free
of any singularity, (and twice continuously differentiable), all the
$\mathbf{O}(D,D)$-symmetric curvatures are automatically regular. In fact, all
our examples satisfy the equations of motion of the NS-NS supergravity,
possibly with an $\mathbf{O}(D,D)$-symmetric “cosmological constant”:

(6)

This readily implies that the corresponding non-singular DFT ansatz (4) solves
the DFT Einstein equations ${G_{AB}+{\cal
J}_{AB}\,\Lambda_{\scriptscriptstyle{\rm{DFT}}}=0}$ everywhere even at the
non-Riemannian points of ${F=0}$. It also means that all the
$\mathbf{O}(D,D)$-symmetric DFT curvatures are trivially regular
Berman:2014hna . Similarly, while the conventional dilaton $\phi$ diverges as
${F\rightarrow 0}$, the DFT dilaton $d$ remains finite, c.f. (4), hence so
does the $\mathbf{O}(D,D)$-symmetric version of the Fradkin–Tseytlin term
Fradkin:1984pq  in doubled string actions Hull:2006va ; Fernandez-
Melgarejo:2018wpg .

###  iii)) Geodesics are complete in string frame:
impenetrable non-Riemannian sphere

The fact that the DFT dilaton $e^{-2d}$ carries a nontrivial diffeomorphic
weight prevents it from coupling to the $\mathbf{O}(D,D)$-symmetric doubled-
yet-gauged particle and string actions Ko:2016dxa ; Lee:2013hma , hence to
particle and stringy geodesics, whose equations read respectively
Morand:2017fnv ; Foot2nd :

$\begin{array}[]{r}\textstyle{e\frac{{{\rm d}}~{}}{{{\rm d}}\tau}(e^{-1}{\cal
H}_{AB}{\rm D}_{\tau}x^{B})+2\Gamma_{ABC}(\bar{P}{\rm D}_{\tau}x)^{B}(P{\rm
D}_{\tau}x)^{C\\!}=0\,,}\\\
\textstyle{\frac{1}{\sqrt{-h}}}\partial_{\alpha}(\sqrt{-h}{\cal H}_{AB}{\rm
D}^{\alpha}x^{B})+\Gamma_{ABC}(\bar{P}{\rm D}_{\alpha}x)^{B}(P{\rm
D}^{\alpha}x)^{C\\!}=0\,,\end{array}$ (7)

where $e,h_{\alpha\beta}$ are the worldline einbein and worldsheet metric,
while $P_{AB},\bar{P}_{AB}$ stand for ${{\textstyle\frac{1}{2}}}({\cal
J}_{AB}\pm{\cal H}_{AB})$ and ${\rm D}_{\tau}x$, ${\rm D}_{\alpha}x$ are the
pull-backs of the doubled-yet-gauged differential. This rigidity naturally
settles the issue of the frame ambiguity. Upon the Riemannian background of
(1), an $\mathbf{O}(D,D)$-symmetric particle follows geodesics defined in the
string frame FootPenrose : after fixing gauges and solving for the auxiliary
connection, (7) can be shown to reproduce the standard (undoubled)
expressions,

$\begin{array}[]{r}\ddot{x}^{\mu}+\gamma^{\mu}_{\nu\rho}\dot{x}^{\nu}\dot{x}^{\rho}=0~{}~{}\Longleftrightarrow~{}~{}\frac{\rm
d~{}}{\rm
d\lambda}(g_{\mu\nu}\dot{x}^{\nu})-{{\textstyle\frac{1}{2}}}\partial_{\mu}g_{\nu\rho}\dot{x}^{\nu}\dot{x}^{\rho}=0\,,\\\
\\!\scalebox{0.92}{$\partial_{+}(g_{\mu\nu}\partial_{-}x^{\nu})+\partial_{-}(g_{\mu\nu}\partial_{+}x^{\nu}){+(}H_{\mu\nu\rho}-\partial_{\mu}g_{\nu\rho})\partial_{+}x^{\nu}\partial_{-}x^{\rho}=0\,.$}\end{array}$
(8)

Focusing on the ansatz (3) and by analogy with ii)), the doubled formulation
(7) in terms of the generalised metric ${\cal H}_{AB}$ may still suggest that
geodesics are regular in the limit $F\rightarrow 0$, despite the fact that its
undoubled counterpart (8) involves the singular Riemannian metric
$g_{\mu\nu}$. Indeed, as we show below for the aforementioned three examples,
both null and time-like geodesics are complete (at least) in the region
${F>0}$. The non-Riemannian points of ${F=0}$ form a sphere for ${D>2}$ (or
hyperbola for ${D=2}$) inside of which (${F<0}$) no time-like nor null
geodesics can penetrate. Time-like and non-radial null geodesics cannot even
come close to the sphere from outside (${F>0}$). Only radial null ones may
approach the sphere with identically vanishing proper velocities taking
infinite affine parameter. Besides, undoubled strings—as an alternative probe
of the “singular” geometries Duff:1991pe ; Duff:1994an —become (anti-)chiral:
with light-cone coordinates $y^{\pm}=y\pm t$ and also
$\partial_{\pm\\!}=\\!\frac{\partial~{}}{\partial\sigma^{\pm}}$ on the
worldsheet, as already used in (8), we get
$\partial_{-}y^{+}=0=\partial_{+}y^{-}$ (or
$\partial_{+}y^{+}=0=\partial_{-}y^{-}$) in the limit ${F\rightarrow 0}$.
Thus, the undoubled, or conventional, particle geodesics and string
propagations agree with the non-Riemannian (freezing/chiral/anti-chiral)
behaviors predicted from the previous doubled-yet-gauged sigma model approach
Lee:2013hma ; Morand:2017fnv  which relied on the auxiliary gauge connection
as Lagrange multiplier (c.f. Introduction).

### ii)) & iii)) again: geodesic deviations are also regular.

In DFT there is no $\mathbf{O}(D,D)$-symmetric completion of the Riemann
curvature Jeon:2010rw ; Jeon:2011cn ; Hohm:2011si . Hence, the criterion of
‘$\mathbf{O}(D,D)$-symmetric curvature singularity’ may appear unbalanced or
somewhat unfair compared to GR. As a step toward restoring the balance as well
as focusing on genuine physical quantities, we further analyse the geodesic
deviation and the ‘tidal force’ therein (again in string frame),

$\scalebox{1.1}{$\frac{\rm{D}^{2}\xi^{\mu}}{{{\rm
d}}\lambda^{2}}$}=R^{\mu}{}_{\nu\rho\sigma}\dot{x}^{\nu}\dot{x}^{\rho}\xi^{\sigma}\,.$
(9)

As the geodesics are complete and smooth for ${F\geq 0}$, their deviations
$\xi^{\mu}$ should be regular. Then, although the Riemann curvature itself
diverges, its contraction with the vanishing velocities
$R^{\mu}{}_{\nu\rho\sigma}\dot{x}^{\nu}\dot{x}^{\rho}$ as well as the square
norm $\big{|}\frac{\rm{D}^{2}\xi}{{{\rm
d}}\lambda^{2}}\big{|}^{2}=g_{\mu\nu}\frac{\rm{D}^{2}\xi^{\mu}}{{{\rm
d}}\lambda^{2}}\frac{\rm{D}^{2}\xi^{\nu}}{{{\rm d}}\lambda^{2}}$ can be
finite, thus preventing the physically measurable quantities from being
singular. This further property will be checked to hold in the following
section for the examples A, B and C.

##  III Examples: geodesics and string propagation

We now take a closer look at each example Witten:1991yr ; Burgess:1994kq ;
Horowitz:1991cd  to analyse generic geodesics (8) supplemented by the
Hamiltonian or Virasoro constraints,

$\begin{array}[]{ll}g_{\mu\nu}\dot{x}^{\mu}\dot{x}^{\nu}={\cal
E}\,,&\qquad\partial_{+}x^{\mu}\partial_{+}x^{\nu}g_{\mu\nu}=0=\partial_{-}x^{\mu}\partial_{-}x^{\nu}g_{\mu\nu}\,.\vspace{-3pt}\end{array}$
(10)

Hereafter, ${\cal E}$ is to be either $-1$ (time-like) or $0$ (null).

###  III.1 ${D=2}$ black hole: non-Riemannian hyperbola

The ${D=2}$ geometry à la Witten Witten:1991yr  is characterised by ${{\rm
d}}s^{2}={{\rm d}}y^{+}{{\rm d}}y^{-}/F$ with
${F=-1+y^{+}y^{-}/l^{2}=\frac{F}{|F|}e^{-2\phi}}$. It solves (6) when
${\Lambda_{\scriptscriptstyle{\rm{DFT}}}=-\frac{2}{l^{2}}}$. From the on-shell
value of the Ricci scalar ${R=-\frac{4}{l^{2}F}}$, the hyperbola
${y^{+}y^{-}=l^{2}}$ corresponds to a curvature singularity. We stress that
though the $H$-flux is trivial in two dimensions, the $B$-field still plays a
crucial role in making the generalised metric free of singularity (5).

Since the metric is invariant under scaling $\delta y^{\pm}=\pm y^{\pm}$,
there are two constants of motion for every geodesic,

$\begin{array}[]{ll}L=(y^{-}\dot{y}^{+}-y^{+}\dot{y}^{-})/F\,,&\quad{\cal
E}=\dot{y}^{+}\dot{y}^{-}/F\,,\end{array}$ (11)

which give, setting ${\omega\equiv{l\dot{y}^{+}}/{y^{+}}}$,

$\begin{array}[]{c}\scalebox{1.0}{$\textstyle{\\!{l\frac{{{\rm d}}F}{{{\rm
d}}\lambda}}\\!=\\!\pm\sqrt{\\!F\\!\left[4{\cal
E}\\!+\\!\left({\frac{L^{2}}{l^{2}}\\!+4{\cal
E}}\right)\\!F\right]}\,,~{}\,{l^{2}{\frac{{{\rm d}}^{2}F}{{{\rm
d}}\lambda^{2}}}}\\!=\\!\left(\\!\frac{L^{2}}{l^{2}}\\!+\\!4{\cal
E}\right)\\!F{+2{\cal E}}\,,}$}\\\ \textstyle{\frac{L^{2}}{l^{2}}+4{\cal
E}=\left(\omega{-\frac{{\cal
E}}{\omega}}\right)^{2\\!}+\left(\frac{\omega}{F}\right)^{2\\!}+\frac{2(\omega^{2}{-{\cal
E}})}{F}\,.}\end{array}$

It follows that time-like geodesics (${{\cal E}=-1}$) starting from the region
${F>0}$ will never reach the non-Riemannian hyperbola, satisfying
${F\geq\frac{4}{(L/l)^{2}-4}>0}$. Null ones (${{\cal E}=0}$) may approach only
at past or future infinity as ${F=e^{\pm L\lambda/l^{2}}F_{0}}$, since the
most general null geodesics are, from (11) with initial values $y^{\pm}_{0}$
and $F_{0}$ at ${\lambda=0}$, either

$\left(\begin{array}[]{c}y^{+}(\lambda)\\\
y^{-}(\lambda)\end{array}\right)=\left(\begin{array}[]{c}l^{2}/y_{0}^{-}+\big{(}y_{0}^{+}-l^{2}/y^{-}_{0}\big{)}e^{L\lambda/l^{2}}\\\
y_{0}^{-}\end{array}\right)\,,$ (12)

or $y^{+}(\lambda)=y_{0}^{+}$,
$y^{-}(\lambda)=l^{2}/y_{0}^{+}+\big{(}y_{0}^{-}-l^{2}/y^{+}_{0}\big{)}e^{-L\lambda/l^{2}}$.
For these two solutions, the only nonvanishing components in (9) are
respectively
$R^{+}{}_{\nu\rho-}\dot{x}^{\nu}\dot{x}^{\rho}=-(L/y_{0}^{-}l)^{2}$ and
$R^{-}{}_{\nu\rho+}\dot{x}^{\nu}\dot{x}^{\rho}=-(L/y_{0}^{+}l)^{2}$, which are
all finite with ${\big{|}\frac{\rm{D}^{2}\xi}{{{\rm
d}}\lambda^{2}}\big{|}^{2}=0}$. In fact, the variations of the general
solutions (12) by the free parameters, $y_{0}^{\pm}$, also lead to finite
deviation vectors, $\xi^{\mu}$. We conclude that the space ${F>0}$ is
geodesically complete with no singular deviation. We turn to the string
dynamics (8), (10) which read

$\begin{array}[]{rr}\partial_{+}\partial_{-}y^{+}-\partial_{+}y^{+}\partial_{-}y^{+}\frac{\partial\ln
F}{\partial y^{+}}=0\,,&\qquad\partial_{+}y^{+}\partial_{+}y^{-}=0\,,\\\
\partial_{+}\partial_{-}y^{-}-\partial_{+}y^{-}\partial_{-}y^{-}\frac{\partial\ln
F}{\partial
y^{-}}=0\,,&\qquad\partial_{-}y^{+}\partial_{-}y^{-}=0\,.\end{array}$

The second relation gives either ${\partial_{+}y^{+}=0}$ or
${\partial_{+}y^{-}=0}$. If ${\partial_{+}y^{+}=0}$, the third implies
${\partial_{+}(\frac{1}{F}\partial_{-}y^{-})=0}$ such that
${\partial_{-}y^{-}=F{\mathbf{f}(\sigma^{-})}}$ for some one-variable function
$\mathbf{f}(\sigma^{-})$. Thus, $\partial_{-}y^{-}$ vanishes when ${F=0}$. On
the other hand, if ${\partial_{+}y^{-}=0}$, the first implies
${\partial_{+}(\frac{1}{F}\partial_{-}y^{+})=0}$ and
${\partial_{-}y^{+}=F\mathbf{f}(\sigma^{-})}$. Thus, $\partial_{-}y^{+}$
vanishes when ${F=0}$. Similar analysis holds for the last relation. We
conclude that, in any case, one of $\\{y^{+},y^{-}\\}$ is chiral and the other
is anti-chiral on the non-Riemannian hyperbola.

###  III.2 ${D=4}$ two-parameter family of spherical solution

Our ${D=4}$ example is a spherical solution from Burgess:1994kq ,

$\begin{array}[]{l}{{\rm d}}s^{2}=\frac{1}{F(r)}\left(-{{\rm d}}t^{2}+{{\rm
d}}r^{2}\right)+{\cal R}(r)^{2}\left({{\rm
d}}\vartheta^{2}+\sin^{2\\!}\vartheta\,{{\rm d}}\varphi^{2}\right)\,,\\\
B_{(2)}=\pm\frac{1}{F(r)}{{\rm d}}t\wedge{{\rm d}}r+h\cos\vartheta\,{{\rm
d}}t\wedge{{\rm d}}\varphi\,,\end{array}\vspace{-2pt}$

where $F(r),{\cal R}(r)^{2}$ are, with two free parameters, $b,h$ Ko:2016dxa
(see also Angus:2018mep  for their physical interpretations),

$\begin{array}[]{l}\frac{1}{F(r)}=\frac{1+\sqrt{1-h^{2}/b^{2}}}{2}\left(\frac{r}{r+b}\right)+\frac{1-\sqrt{1-h^{2}/b^{2}}}{2}\left(\frac{r+b}{r}\right)\,,\\\
{\cal
R}(r)^{2}=\big{(}r+\frac{1}{2}b-\frac{1}{2}\sqrt{b^{2}-h^{2}}\big{)}^{2}+\frac{1}{4}h^{2}=\frac{r(r+b)}{F(r)}\,.\end{array}$
(13)

We require $0<|h|\leq b$, such that the only singular source in the metric is
at ${r=0}$ as $\lim_{r\rightarrow 0}F(r)=0$. The Ricci scalar diverges at
${r=0}$ as
$R\simeq-\frac{2}{\left(b-\sqrt{b^{2}-h^{2}}\right)\scalebox{1.0}{$r$}\,}$.
Nevertheless, with non-singular ${\cal R}(0)^{-2}$ due to ${h\neq 0}$, the
generalised metric ${\cal H}_{AB}$, dilaton $e^{-2d}={\cal
R}(r)^{2}\sin\vartheta$, and DFT curvatures are all finitely regular. The non-
Riemannian points of ${F=0}$ form a $2$-sphere with nontrivial proper area
$4\pi{\cal R}(0)^{2}=2\pi b(b-\sqrt{b^{2}-h^{2}})$.

For geodesics, without loss of generality, we put ${\vartheta=\frac{\pi}{2}}$.
The conserved energy $E$ and angular momentum $L_{\varphi}$ set

$\begin{array}[]{ll}\dot{t}=EF(r)\,,&\qquad\dot{\varphi}=L_{\varphi}{\cal
R}(r)^{-2}\,.\end{array}\vspace{-2pt}$ (14)

In particular, $\dot{t}$ vanishes on the non-Riemannian sphere. The remaining
radial motion reads

$\begin{array}[]{ll}0=\dot{r}^{2}+V(r)\,,&\quad V(r)=\left[-{\cal
E}-E^{2}F(r)+\frac{L_{\varphi}^{2}}{{\cal
R}(r)^{2}}\right]\\!F(r)\,.\end{array}$

From ${\lim_{r\rightarrow 0}V=0}$, it follows that $\dot{r}$ also gets trivial
at ${r=0}$. In fact, since $\lim_{r\rightarrow
0}V^{\prime}(r)=\frac{4L_{\varphi}^{2}}{b(b-\sqrt{b^{2}-h^{2}})^{2}}-\frac{2{\cal
E}}{b-\sqrt{b^{2}-h^{2}}}$ is positive for either ${{\cal E}=-1}$, or ${{\cal
E}=0}$ with ${L_{\varphi}\neq 0}$, the corresponding potential is positive
close to ${r=0^{+}}$. Thus, both the time-like and the non-radial null
geodesics cannot come close to the sphere from outside. Only the radial null
ones with ${{\cal E}=0=L_{\varphi}}$ may do, but it takes infinite affine
parameter as the integral of ${{\rm d}}\lambda=(EF)^{-1}{{\rm d}}r$ diverges
logarithmically. These results can be all attributed to the repulsive
gravitational force around the non-Riemannian sphere, while it is attractive
for large $r\sim{\cal R}$ as $g_{tt}\sim-1+\frac{b\sqrt{1-h^{2}/b^{2}}}{{\cal
R}}$.

For the radial null geodesics $\dot{t}=EF=|\dot{r}|$, we also confirm that the
deviation (9) is finitely regular: the only nontrivial components of
$R^{\mu}{}_{\nu\rho\sigma}\dot{x}^{\nu}\dot{x}^{\rho}$ at ${r=0}$ take the
values $\frac{\pm 2E^{2}}{(b-\sqrt{b^{2}-h^{2}})^{2}}$ for $\mu,\sigma$ being
$t$ or $r$, with ${\big{|}\frac{\rm{D}^{2}\xi}{{{\rm
d}}\lambda^{2}}\big{|}^{2}=0}$.

In the limit, ${r\rightarrow 0}$ hence ${F\rightarrow 0}$, the string dynamics
(8), (10) implies, with $y^{\pm}=r\pm t$,

$\vspace{-3pt}\begin{array}[]{ll}\partial_{+}y^{+}\partial_{-}y^{+}F^{\prime}(0)=0\,,&\qquad\partial_{+}y^{+}\partial_{+}y^{-}=0\,,\\\
\partial_{+}y^{-}\partial_{-}y^{-}F^{\prime}(0)=0\,,&\qquad\partial_{-}y^{+}\partial_{-}y^{-}=0\,,\end{array}\vspace{-2pt}$
(15)

where $F^{\prime}(0)={\lim_{r\rightarrow
0}}F^{\prime}(r)=\textstyle{\frac{2}{b-\sqrt{b^{2}-h^{2}}}}$ is nonvanishing.
This confirms that one of $\\{y^{+},y^{-}\\}$ is chiral while the other is
anti-chiral on the non-Riemannian sphere.

###  III.3 ${D=10}$ black ${5}$-brane

One particular black $5$-brane geometry from Horowitz:1991cd  reads

$\vspace{-2pt}\begin{array}[]{ll}\\!{{\rm d}}s^{2}=\frac{-{{\rm d}}t^{2}+{{\rm
d}}r^{2}}{F(r)}+r^{2}{{\rm d}}\Omega_{3}^{2}+{{\rm
d}}\vec{x}^{\,2}\,,&~{}\,\scalebox{0.95}{$F=1{-({r_{c}/r})^{2}}=e^{-2\phi}$}\,.\end{array}$

The Ricci scalar diverges both at ${r=0}$ and ${r=r_{c}}$ as
$R=-\frac{4r_{c}^{4}}{r^{4}(r^{2}-r_{c}^{2})}$. Though the $H$-flux is
trivial, a pure gauge $B$-field should be introduced, as prescribed in (3).
The generalised metric (5) is then non-Riemannian regular on the $3$-sphere of
the radius ${r=r_{c}}$, but still singular at ${r=0}$. We shall see soon that
the non-Riemannian sphere forms the boundary of a geodesically complete space
of ${F>0}$ which excludes the dangerous point ${r=0}$.

The geodesic analysis is similar to example B and reduces to $\dot{t}=EF$ and
$\dot{r}^{2}+V(r)=0$ with a potential involving non-negative constants,
$L_{\Omega}^{2}$ (total angular momentum) and ${\vec{P}}^{2}$ (extra
momentum),

$\vspace{-2pt}V(r)=\left[\scalebox{1.0}{$-{\cal
E}-E^{2}F(r)+\frac{L_{\Omega}^{2}}{r^{2}}+{\vec{P}}^{2}$}\right]\\!F(r)\,.$

Since $V^{\prime}(r_{c})=2(-{\cal
E}+L_{\Omega}^{2}/r_{c}^{2}+{\vec{P}}^{2})/r_{c}$ is positive for either
${{\cal E}=-1}$ or ${{\cal E}=0}$ with
$L_{\Omega}^{2}/r_{c}^{2}+{\vec{P}}^{2}\neq 0$, and ${V(r_{c})}$ vanishes, the
corresponding potential is positive close to ${r=r_{c}^{+}}$. Thus, time-like
and generic null geodesics cannot reach the non-Riemannian sphere. Only the
radial null ones having $\dot{t}=EF=|\dot{r}|$ and
$L_{\Omega}^{2}=0={\vec{P}}^{2}$ can do, albeit taking infinite affine
parameter with vanishing proper velocities. Besides, the deviation (9) is
regular: the only nontrivial values of
$R^{\mu}{}_{\nu\rho\sigma}\dot{x}^{\nu}\dot{x}^{\rho}$ at ${r=r_{c}}$ are $\pm
2E^{2}/r_{c}^{2}$, for $\mu,\sigma$ being $t$ or $r$, with
${\big{|}\frac{\rm{D}^{2}\xi}{{{\rm d}}\lambda^{2}}\big{|}^{2}=0}$.

In the limit ${r\rightarrow r_{c}}$ hence ${F\rightarrow 0}$, the chirality
relations of the previous example (15) still hold after replacing
$F^{\prime}(0)$ by $F^{\prime}(r_{c})=2/r_{c}$.

## Discussion

We have shown that the curvature singularities featured in a large class of GR
spacetimes (3) are mere artifacts of Riemannian geometry. In particular, we
have noted the remarkable fact that physically measurable tidal forces do not
diverge. Further examples include ${D=10}$ superstring Dabholkar:1990yf ;
Berkeley:2014nza  with negative tension Dijkgraaf:2016lym ;
Arvanitakis:2016zes ; Blair:2016xnn ; Berman:2019izh ; Blair:2019qwi . The
corresponding generalised metric was shown to be regular in Blair:2016xnn .

Converted to the Einstein frame, $g^{\rm{\bf
E}}_{\mu\nu}=e^{4\phi/(2-D)}g_{\mu\nu}$, the ${D>2}$ examples feature more
severe curvature singularities and become geodesically incomplete e.g.
Kang:2019owv , with singular deviations. ${D=2}$ DFT is essentially
Jackiw–Teitelboim gravity Teitelboim:1983ux ; Jackiw:1984je  as $g^{\rm{\bf
JT}}_{\mu\nu}=e^{-2\phi}g_{\mu\nu}$. Witten’s solution is then mapped to flat
spacetime.

Constant non-Riemannian backgrounds were shown in Blair:2020gng  to admit
infinite-dimensional isometries. All of them might be realised as the
asymptotic symmetries of the non-Riemannian spheres with large radius (as
${F^{\prime}\rightarrow 0}$). The associated, infinitely many, conserved
charges then might store all the information of the in-going and freezing null
radial geodesics. We call for further studies.

Acknowledgments. We wish to thank Gungwon Kang, Nakwoo Kim, Wontae Kim, and
Dong-han Yeom for useful discussions as well as anonymous referees for helpful
suggestions. This work is supported by Basic Science Research Program through
the National Research Foundation of Korea (NRF) through the grants,
NRF-2016R1D1A1B01015196, NRF-2018H1D3A1A01030137 (Brain Pool Program),
NRF-2020R1A6A1A03047877 (Center for Quantum Space Time), and
NRF-2021R1C1C1005037. MP was further supported by a KIAS Individual Grant
(PG062002) at Korea Institute for Advanced Study and by the Institute for
Basic Science (Grant No. IBS-R018-Y1).

Supplemental Material

##  ${D=10}$ fundamental string with negative tension

We now expound on the aforementioned example of the fundamental string
Dabholkar:1990yf ,

$\begin{array}[]{ll}{{\rm d}}s^{2}=\frac{{{\rm d}}y^{+}{{\rm
d}}y^{-}}{F(r)}+{{\rm d}}\vec{x}^{\,2}\,,&\quad B_{(2)}=\frac{{{\rm
d}}y^{+}\wedge{{\rm d}}y^{-}}{2F(r)}\,,\vspace{-2pt}\end{array}$

where ${F=1+\frac{Q}{r^{6}}=e^{-2\phi}}$ is a harmonic function and
${r^{2}=\vec{x}{\cdot\vec{x}}}$. The Ricci scalar diverges at ${r=0}$ as
$R=-\frac{126Q^{2}}{r^{2}(Q+r^{6})^{2}}$, and further at $r=|Q|^{1/6}$
provided that the tension is negative, ${Q<0}$. The corresponding generalised
metric—identified as a doubled null wave in Berkeley:2014nza —is then non-
Riemannian regular at $r=|Q|^{1/6}$ Berman:2019izh ; Blair:2019qwi  but still
singular at ${r=0}$. Similarly to examples B and C, the non-Riemannian
$7$-sphere of radius ${r=|Q|^{1/6}}$ forms the boundary of the geodesically
complete space ${F\geq 0}$, which thus excludes the dangerous point ${r=0}$.

The longitudinal isometries give two constants of motion $P_{\pm}$ and set
${\dot{y}^{\pm}=P_{\pm}F}$ which clearly vanish when ${F=0}$. Moreover, time-
like and also non-radial (${L^{2}>0}$) null geodesics are incompatible with
${F=0}$, due to the fact that
${|\dot{\vec{x}}|^{2}=\dot{r}^{2}+\frac{L^{2}}{r^{2}}={\cal E}-P_{+}P_{-}F}$
is non-negative. Hence ${P_{+}P_{-}\leq 0}$ and the acceleration
$\ddot{\vec{x}}=-3|Q|P_{+}P_{-}\vec{x}/r^{8}$ is repulsive. Radial
(${L^{2}=0}$) null ones with ${P_{+}P_{-}<0}$ may reach the sphere only to
bounce back within finite affine parameter. On the contrary, null ones with
${P_{+}P_{-}=0}$ have ${\dot{\vec{x}}=0}$ and thus $r$ is fixed for ever. In
particular, when ${r=|Q|^{1/6}}$, from ${\dot{x}^{\mu}=0}$, $x^{\mu}$ should
be (trivially) constant. Anyhow, time-like and null geodesics are all
complete. We turn to the deviations of the bouncing null geodesics,

$\begin{array}[]{l}y^{\pm}(\lambda)\,\simeq\,y^{\pm}_{0}-3|Q|^{-\frac{1}{3}}P_{\pm}P_{+}P_{-}\lambda^{3}\,,\\\
{\vec{x}}(\lambda)\,\simeq\,\hat{n}_{0}\\!\left(|Q|^{\frac{1}{6}}-\frac{3}{2}|Q|^{-\frac{1}{6}}P_{+}P_{-}\lambda^{2}\right)\,.\end{array}\vspace{-2pt}$
(16)

This expansion around the bouncing at ${\lambda=0}$ comes from $F\simeq
6(r|Q|^{-1/6}-1)$, and features all possible constants of motion:
$P_{\pm},y^{\pm}_{0}$ and a unit vector $\hat{n}_{0}$. Varying each of them,
we acquire a deviation vector $\xi^{\mu}$. Contrarily to the previous
examples, some of $R^{\mu}{}_{\nu\rho\sigma}\dot{x}^{\nu}\dot{x}^{\rho}$’s
exhibit singularities as severe as ${F^{-3/2}\propto\lambda^{-3}}$ for
${\sigma=\pm}$, or ${F^{-1}\propto\lambda^{-2}}$ for transverse $\sigma$.
Nonetheless, the full expression of the tidal force
$R^{\mu}{}_{\nu\rho\sigma}\dot{x}^{\nu}\dot{x}^{\rho}\xi^{\sigma}$ is finite,
once contracted with the deviation vectors of (16) induced by
$\delta{(P_{+}/P_{-})=0}$ (dilation, ${\xi^{\mu}=\lambda\dot{x}^{\mu}}$),
$\delta{(P_{+}P_{-})=0}$ $(\mathbf{so}(1,1)$ Lorentz),
${\delta\hat{n}_{0}\cdot{\vec{x}}=0}$ $(\mathbf{so}(8)$ rotation), with the
exception of $\delta y_{0}^{\pm}$ (translation). Translational $\xi^{\mu}$’s
are just constant. Being longitudinal, their proper length gets singular, and
subsequently so does the tidal force acting on them. Lastly, the string
propagation (8) gives

$\partial_{+}(F^{-1}\partial_{-}y^{+})=0=\partial_{-}(F^{-1}\partial_{+}y^{-})\,,$
(17)

which yields
${\partial_{-}y^{+}=F{\mathbf{f_{\scriptscriptstyle{-}}}(\sigma^{-})}}$ and
${\partial_{+}y^{-}=F{\mathbf{f_{\scriptscriptstyle{+}}}(\sigma^{+})}}$,
naturally implying the (anti-)chirality at ${r=|Q|^{1/6}}$.

## References

  * (1) R. Penrose, “Gravitational collapse and space-time singularities,” Phys. Rev. Lett. 14 (1965), 57-59 doi:10.1103/PhysRevLett.14.57
  * (2) G. J. Olmo, D. Rubiera-Garcia and A. Sanchez-Puente, “Geodesic completeness in a wormhole spacetime with horizons,” Phys. Rev. D 92 (2015) no.4, 044047 doi:10.1103/PhysRevD.92.044047 [arXiv:1508.03272 [hep-th]].
  * (3) V. Faraoni, E. Gunzig and P. Nardone, “Conformal transformations in classical gravitational theories and in cosmology,” Fund. Cosmic Phys. 20 (1999), 121 [arXiv:gr-qc/9811047 [gr-qc]].
  * (4) V. Faraoni and S. Nadeau, “The (pseudo)issue of the conformal frame revisited,” Phys. Rev. D 75 (2007), 023501 doi:10.1103/PhysRevD.75.023501 [arXiv:gr-qc/0612075 [gr-qc]].
  * (5) G. W. Horndeski, “Second-order scalar-tensor field equations in a four-dimensional space,” Int. J. Theor. Phys. 10 (1974), 363-384 doi:10.1007/BF01807638
  * (6) T. H. Buscher, “A Symmetry of the String Background Field Equations,” Phys. Lett. B 194 (1987) 59.
  * (7) T. H. Buscher, “Path Integral Derivation of Quantum Duality in Nonlinear Sigma Models,” Phys. Lett. B 201 (1988) 466.
  * (8) A. Giveon, E. Rabinovici and G. Veneziano, “Duality in String Background Space,” Nucl. Phys. B 322 (1989), 167-184 doi:10.1016/0550-3213(89)90489-6
  * (9) M. Duff, “Duality Rotations in String Theory,” Nucl. Phys. B 335 (1990), 610
  * (10) A. A. Tseytlin, “Duality Symmetric Formulation Of String World Sheet Dynamics,” Phys. Lett. B 242, 163 (1990).
  * (11) A. A. Tseytlin, “Duality Symmetric Closed String Theory And Interacting Chiral Scalars,” Nucl. Phys. B 350, 395 (1991).
  * (12) M. Rocek and E. P. Verlinde, “Duality, quotients, and currents,” Nucl. Phys. B 373 (1992) 630 [hep-th/9110053].
  * (13) A. Giveon and M. Rocek, “Generalized duality in curved string backgrounds,” Nucl. Phys. B 380 (1992) 128 [hep-th/9112070].
  * (14) C. M. Hull, “A Geometry for non-geometric string backgrounds,” JHEP 0510 (2005) 065 [hep-th/0406102].
  * (15) C. M. Hull, “Global aspects of T-duality, gauged sigma models and T-folds,” JHEP 0710 (2007) 057 [hep-th/0604178].
  * (16) C. M. Hull, “Doubled Geometry and T-Folds,” JHEP 0707 (2007) 080 [hep-th/0605149].
  * (17) W. Siegel, “Two vierbein formalism for string inspired axionic gravity,” Phys. Rev. D 47 (1993) 5453 [hep-th/9302036].
  * (18) W. Siegel, “Superspace duality in low-energy superstrings,” Phys. Rev. D 48 (1993) 2826 [hep-th/9305073].
  * (19) C. Hull and B. Zwiebach, “Double Field Theory,” JHEP 0909 (2009) 099 [arXiv:0904.4664 [hep-th]].
  * (20) C. Hull and B. Zwiebach, JHEP 0909 (2009) 090 [arXiv:0908.1792 [hep-th]].
  * (21) O. Hohm, C. Hull and B. Zwiebach, “Background independent action for double field theory,” JHEP 1007 (2010) 016 [arXiv:1003.5027 [hep-th]].
  * (22) O. Hohm, C. Hull and B. Zwiebach, JHEP 08 (2010), 008 [arXiv:1006.4823 [hep-th]].
  * (23) K. Lee and J. H. Park, “Covariant action for a string in doubled yet gauged spacetime,” Nucl. Phys. B 880 (2014) 134 [arXiv:1307.8377 [hep-th]].
  * (24) K. Morand and J. H. Park, “Classification of non-Riemannian doubled-yet-gauged spacetime,” Eur. Phys. J. C 77 (2017) no.10, 685 [arXiv:1707.03713 [hep-th]].
  * (25) K. Cho and J. H. Park, “Remarks on the non-Riemannian sector in Double Field Theory,” Eur. Phys. J. C 80 (2020) no.2, 101 doi:10.1140/epjc/s10052-020-7648-9 [arXiv:1909.10711 [hep-th]].
  * (26) J. H. Park and S. Sugimoto, “String Theory and non-Riemannian Geometry,” Phys. Rev. Lett. 125 (2020) no.21, 211601 doi:10.1103/PhysRevLett.125.211601 [arXiv:2008.03084 [hep-th]].
  * (27) I. Jeon, K. Lee and J. H. Park, “Stringy differential geometry, beyond Riemann,” Phys. Rev. D 84 (2011) 044022 doi:10.1103/PhysRevD.84.044022 [arXiv:1105.6294 [hep-th]].
  * (28) J. H. Park, S. J. Rey, W. Rim and Y. Sakatani, “$\mathbf{O}(D,D)$ covariant Noether currents and global charges in double field theory,” JHEP 1511 (2015) 131 [arXiv:1507.07545 [hep-th]].
  * (29) S. Angus, K. Cho and J. H. Park, “Einstein Double Field Equations,” Eur. Phys. J. C 78 (2018) no.6, 500 doi:10.1140/epjc/s10052-018-5982-y [arXiv:1804.00964 [hep-th]].
  * (30) J. Gomis and H. Ooguri, “Nonrelativistic closed string theory,” J. Math. Phys. 42 (2001), 3127-3151 doi:10.1063/1.1372697 [arXiv:hep-th/0009181 [hep-th]].
  * (31) U. H. Danielsson, A. Guijosa and M. Kruczenski, “IIA/B, wound and wrapped,” JHEP 10 (2000), 020 doi:10.1088/1126-6708/2000/10/020 [arXiv:hep-th/0009182 [hep-th]].
  * (32) J. Gomis, J. Gomis and K. Kamimura, “Non-relativistic superstrings: A New soluble sector of $AdS(5)\times S^{5}$,” JHEP 12 (2005), 024 doi:10.1088/1126-6708/2005/12/024 [arXiv:hep-th/0507036 [hep-th]].
  * (33) M. H. Christensen, J. Hartong, N. A. Obers and B. Rollier, “Torsional Newton-Cartan Geometry and Lifshitz Holography,” Phys. Rev. D 89 (2014), 061901(R) doi:10.1103/PhysRevD.89.061901 [arXiv:1311.4794 [hep-th]].
  * (34) J. Hartong and N. A. Obers, “Hořava-Lifshitz gravity from dynamical Newton-Cartan geometry,” JHEP 07 (2015), 155 doi:10.1007/JHEP07(2015)155 [arXiv:1504.07461 [hep-th]].
  * (35) T. Harmark, J. Hartong and N. A. Obers, “Nonrelativistic strings and limits of the AdS/CFT correspondence,” Phys. Rev. D 96 (2017) no.8, 086019 doi:10.1103/PhysRevD.96.086019 [arXiv:1705.03535 [hep-th]].
  * (36) T. Harmark, J. Hartong, L. Menculini, N. A. Obers and Z. Yan, “Strings with Non-Relativistic Conformal Symmetry and Limits of the AdS/CFT Correspondence,” JHEP 11 (2018), 190 doi:10.1007/JHEP11(2018)190 [arXiv:1810.05560 [hep-th]].
  * (37) E. Bergshoeff, J. Gomis and Z. Yan, “Nonrelativistic String Theory and T-Duality,” JHEP 11 (2018), 133 doi:10.1007/JHEP11(2018)133 [arXiv:1806.06071 [hep-th]].
  * (38) E. A. Bergshoeff, J. Gomis, J. Rosseel, C. Şimşek and Z. Yan, “String Theory and String Newton-Cartan Geometry,” J. Phys. A 53 (2020) no.1, 014001 doi:10.1088/1751-8121/ab56e9 [arXiv:1907.10668 [hep-th]].
  * (39) T. Harmark, J. Hartong, L. Menculini, N. A. Obers and G. Oling, “Relating non-relativistic string theories,” JHEP 11 (2019), 071 doi:10.1007/JHEP11(2019)071 [arXiv:1907.01663 [hep-th]].
  * (40) E. A. Bergshoeff, J. Lahnsteiner, L. Romano, J. Rosseel and C. Şimşek, “A Non-Relativistic Limit of NS-NS Gravity,” [arXiv:2102.06974 [hep-th]].
  * (41) S. M. Ko, C. Melby-Thompson, R. Meyer and J. H. Park, “Dynamics of Perturbations in Double Field Theory & Non-Relativistic String Theory,” JHEP 12 (2015), 144 doi:10.1007/JHEP12(2015)144 [arXiv:1508.01121 [hep-th]].
  * (42) J. H. Park, “Green-Schwarz superstring on doubled-yet-gauged spacetime,” JHEP 11 (2016), 005 doi:10.1007/JHEP11(2016)005 [arXiv:1609.04265 [hep-th]].
  * (43) D. S. Berman, C. D. A. Blair and R. Otsuki, “Non-Riemannian geometry of M-theory,” JHEP 07 (2019), 175 doi:10.1007/JHEP07(2019)175 [arXiv:1902.01867 [hep-th]].
  * (44) C. D. A. Blair, “A worldsheet supersymmetric Newton-Cartan string,” JHEP 10 (2019), 266 doi:10.1007/JHEP10(2019)266 [arXiv:1908.00074 [hep-th]].
  * (45) A. D. Gallegos, U. Gürsoy, S. Verma and N. Zinnato, “Non-Riemannian gravity actions from double field theory,” [arXiv:2012.07765 [hep-th]].
  * (46) C. D. A. Blair, G. Oling and J. H. Park, “Non-Riemannian isometries from double field theory,” JHEP 04 (2021), 072 doi:10.1007/JHEP04(2021)072 [arXiv:2012.07766 [hep-th]].
  * (47) C. D. A. Blair, D. Gallegos and N. Zinnato, “A non-relativistic limit of M-theory and 11-dimensional membrane Newton-Cartan,” [arXiv:2104.07579 [hep-th]].
  * (48) I. Jeon, K. Lee, J. H. Park and Y. Suh, “Stringy Unification of Type IIA and IIB Supergravities under N=2 D=10 Supersymmetric Double Field Theory,” Phys. Lett. B 723 (2013), 245-250 doi:10.1016/j.physletb.2013.05.016 [arXiv:1210.5078 [hep-th]].
  * (49) A. Coimbra, C. Strickland-Constable and D. Waldram, “Supergravity as Generalised Geometry I: Type II Theories,” JHEP 11 (2011), 091 doi:10.1007/JHEP11(2011)091 [arXiv:1107.1733 [hep-th]].
  * (50) M. Hatsuda, K. Kamimura and W. Siegel, “Type II chiral affine Lie algebras and string actions in doubled space,” JHEP 09 (2015), 113 doi:10.1007/JHEP09(2015)113 [arXiv:1507.03061 [hep-th]].
  * (51) J. H. Park, “Comments on double field theory and diffeomorphisms,” JHEP 06 (2013), 098 doi:10.1007/JHEP06(2013)098 [arXiv:1304.5946 [hep-th]].
  * (52) J. H. Park, “Stringy Gravity: Solving the Dark Problems at ‘short’ distance,” EPJ Web Conf. 168 (2018) 01010 doi:10.1051/epjconf/201816801010 [arXiv:1707.08961 [hep-th]].
  * (53) S. M. Ko, J. H. Park and M. Suh, “The rotation curve of a point particle in stringy gravity,” JCAP 06 (2017), 002 doi:10.1088/1475-7516/2017/06/002 [arXiv:1606.09307 [hep-th]].
  * (54) T. Basile, E. Joung and J. H. Park, “A note on Faddeev–Popov action for doubled-yet-gauged particle and graded Poisson geometry,” JHEP 02 (2020), 022 doi:10.1007/JHEP02(2020)022 [arXiv:1910.13120 [hep-th]].
  * (55) E. Malek, “Timelike U-dualities in Generalised Geometry,” JHEP 11 (2013), 185 doi:10.1007/JHEP11(2013)185 [arXiv:1301.0543 [hep-th]].
  * (56) C. D. A. Blair, “Doubled strings, negative strings and null waves,” JHEP 11 (2016), 042 doi:10.1007/JHEP11(2016)042 [arXiv:1608.06818 [hep-th]].
  * (57) D. S. Berman and F. J. Rudolph, “Strings, Branes and the Self-dual Solutions of Exceptional Field Theory,” JHEP 05 (2015), 130 doi:10.1007/JHEP05(2015)130 [arXiv:1412.2768 [hep-th]].
  * (58) E. Witten, “On string theory and black holes,” Phys. Rev. D 44 (1991), 314-324 doi:10.1103/PhysRevD.44.314
  * (59) C. P. Burgess, R. C. Myers and F. Quevedo, “On spherically symmetric string solutions in four-dimensions,” Nucl. Phys. B 442 (1995), 75-96 doi:10.1016/S0550-3213(95)00090-9 [arXiv:hep-th/9410142 [hep-th]].
  * (60) G. T. Horowitz and A. Strominger, “Black strings and P-branes,” Nucl. Phys. B 360 (1991), 197-209 doi:10.1016/0550-3213(91)90440-9
  * (61) C. D. A. Blair, “Conserved Currents of Double Field Theory,” JHEP 04 (2016), 180 doi:10.1007/JHEP04(2016)180 [arXiv:1507.07541 [hep-th]].
  * (62) E. S. Fradkin and A. A. Tseytlin, “Effective Field Theory from Quantized Strings,” Phys. Lett. B 158 (1985), 316-322 doi:10.1016/0370-2693(85)91190-6
  * (63) J. J. Fernández-Melgarejo, J. I. Sakamoto, Y. Sakatani and K. Yoshida, “Weyl invariance of string theories in generalized supergravity backgrounds,” Phys. Rev. Lett. 122 (2019) no.11, 111602 doi:10.1103/PhysRevLett.122.111602 [arXiv:1811.10600 [hep-th]].
  * (64) The 2nd formula in (7) holds for $(0,0)$ Riemannian cases where the self-duality ${\rm D}_{\alpha}x^{A}+\frac{1}{\sqrt{-h}}\epsilon_{\alpha}{}^{\beta}{\cal H}^{A}{}_{B}{\rm D}_{\beta}x^{B}=0$ is valid for all $A$. For the general expression, see Lee:2013hma .
  * (65) Since the null energy condition can be broken by the term $2{\bigtriangledown}_{\mu}(\partial_{\nu}\phi)$ in (6), Penrose theorem can be evaded in the string frame, thus allowing for geodesically complete spaces.
  * (66) M. J. Duff, R. R. Khuri and J. X. Lu, “String and five-brane solitons: Singular or nonsingular?,” Nucl. Phys. B 377 (1992), 281-294 doi:10.1016/0550-3213(92)90025-7 [arXiv:hep-th/9112023 [hep-th]].
  * (67) M. J. Duff, R. R. Khuri and J. X. Lu, “String solitons,” Phys. Rept. 259 (1995), 213-326 doi:10.1016/0370-1573(95)00002-X [arXiv:hep-th/9412184 [hep-th]].
  * (68) I. Jeon, K. Lee and J. H. Park, “Differential geometry with a projection: Application to double field theory,” JHEP 1104 (2011) 014 doi:10.1007/JHEP04(2011)014 [arXiv:1011.1324 [hep-th]].
  * (69) O. Hohm and B. Zwiebach, “On the Riemann Tensor in Double Field Theory,” JHEP 05 (2012), 126 doi:10.1007/JHEP05(2012)126 [arXiv:1112.5296 [hep-th]].
  * (70) A. Dabholkar, G. W. Gibbons, J. A. Harvey and F. Ruiz Ruiz, “Superstrings and Solitons,” Nucl. Phys. B 340 (1990), 33-55 doi:10.1016/0550-3213(90)90157-9
  * (71) J. Berkeley, D. S. Berman and F. J. Rudolph, “Strings and Branes are Waves,” JHEP 06 (2014), 006 doi:10.1007/JHEP06(2014)006 [arXiv:1403.7198 [hep-th]].
  * (72) R. Dijkgraaf, B. Heidenreich, P. Jefferson and C. Vafa, “Negative Branes, Supergroups and the Signature of Spacetime,” JHEP 02 (2018), 050 doi:10.1007/JHEP02(2018)050 [arXiv:1603.05665 [hep-th]].
  * (73) A. S. Arvanitakis and C. D. A. Blair, “Black hole thermodynamics, stringy dualities and double field theory,” Class. Quant. Grav. 34 (2017) no.5, 055001 doi:10.1088/1361-6382/aa5a59 [arXiv:1608.04734 [hep-th]].
  * (74) S. Kang and D. h. Yeom, “Causal structures and dynamics of black-hole-like solutions in string theory,” Eur. Phys. J. C 79 (2019) no.11, 927 doi:10.1140/epjc/s10052-019-7435-7 [arXiv:1901.06857 [gr-qc]].
  * (75) C. Teitelboim, “Gravitation and Hamiltonian Structure in Two Space-Time Dimensions,” Phys. Lett. B 126 (1983), 41-45 doi:10.1016/0370-2693(83)90012-6
  * (76) R. Jackiw, “Lower Dimensional Gravity,” Nucl. Phys. B 252 (1985), 343-356 doi:10.1016/0550-3213(85)90448-1


# On the Longest Flip Sequence to Untangle Segments in the Plane††thanks: A
version of this paper appears in Walcom’23. This work is supported by the
French ANR PRC grant ADDS (ANR-19-CE48-0005).

Guilherme D. da Fonseca Aix-Marseille Université and LIS, France.
<EMAIL_ADDRESS>Yan Gerard Université Clermont Auvergne and
LIMOS, France. {yan.gerard<EMAIL_ADDRESS>Bastien Rivier$\ddagger$

###### 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 $\mathbf{D}(n)$
of flips performed on $n$ segments. First, we present reductions relating
$\mathbf{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
$\mathbf{D}(n)=\mathcal{O}(tn^{2})$, providing a smooth transition between the
convex $\mathcal{O}(n^{2})$ bound and the general $\mathcal{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
$\mathcal{O}(n^{8/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.

(a) (b) (c)

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

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 $\mathbf{D}_{\mathtt{TSP}}(n)$ denote the maximum number of
flips successively performed on a TSP tour with $n$ segments. An upper bound
of $\mathbf{D}_{\mathtt{TSP}}(n)=\mathcal{O}(n^{3})$ is proved in [30], while
the best lower bound known is $\mathbf{D}_{\mathtt{TSP}}(n)=\Omega(n^{2})$. In
contrast, if the points $P$ are in convex position, then tight bounds of
$\Theta(n^{2})$ 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 $2n$ 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
$\mathbf{D}_{\mathtt{MM}}(n)$ denote the maximum number of flips successively
performed on a monochromatic matching with $n$ segments. In Section 2, we show
that
$\mathbf{D}_{\mathtt{MM}}(n)\leq\mathbf{D}_{\mathtt{TSP}}(3n)\leq\mathbf{D}_{\mathtt{MM}}(3n)$,
hence it suffices to prove asymptotic bounds for $\mathbf{D}_{\mathtt{MM}}(n)$
in order to bound $\mathbf{D}_{\mathtt{TSP}}(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 $\mathbf{D}_{\mathtt{RB}}(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
$\mathbf{D}_{\mathtt{MM}}(n)\leq\mathbf{D}_{\mathtt{RB}}(2n)\leq\mathbf{D}_{\mathtt{MM}}(2n)$
and, as a consequence, asymptotic bounds for the monochromatic matching
version also extend to the red-blue matching version. We use the notation
$\mathbf{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,
$\mathbf{D}(n)=\Theta(n^{2})$ [6, 8]. This tight bound contrasts with the gap
for the general case bounds.

For all three versions in the convex case, $\mathbf{D}(n)\leq\binom{n}{2}$ as
the number of crossings decreases at each flip. The authors have recently
shown that without convexity $\mathbf{D}_{\mathtt{RB}}(n)\geq
1.5\binom{n}{2}-\frac{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 $\Theta(n^{2})$ as the convex bounds. Unfortunately, the best upper bound
known for the non-convex case remains $\mathbf{D}(n)=\mathcal{O}(n^{3})$ [30]
since 1981111While the paper considers only the TSP version, the proof of the
upper bound also works for the matching versions, as shown in [8]., despite
recent work on this specific problem [6, 8, 12]. The best lower bound known is
$\mathbf{D}(n)=\Omega(n^{2})$ [8, 12].

The argument for the convex case bound of $\mathbf{D}(n)\leq\binom{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
$\mathcal{O}(tn^{2})$.

Finally, in Section 4, we use a balancing argument similar to the one of Erdös
et al. [15] to show that if, instead of counting the number of flips, we count
the number of distinct flips (two flips are the same if they change the same
set of four segments), then we get a bound of $\mathcal{O}(n^{8/3})$.

###  1.1 Related Reconfiguration Problems

Combinatorial reconfiguration studies the step-by-step transition from one
solution to another, for a given combinatorial problem. Many reconfiguration
problems are presented in [29].

It may be tempting to use an alternative definition for a flip in order to
remove crossings and reduce the length of a TSP tour. The _2OPT flip_ is not
restricted to crossing segments, as long as it decreases the Euclidean length
of the tour. However, the number of 2OPT flips performed may be exponential
[14].

Another important parameter $\mathbf{d}(n)$ is the _minimum_ number of flips
needed to remove crossings from any set of $n$ segments. When the points are
in convex position, then it is known that $\mathbf{d}(n)=\Theta(n)$ in all
three versions [6, 12, 26, 32]. If the red points are on a line, then
$\mathbf{d}_{\texttt{RB}}(n)=\mathcal{O}(n^{2})$ [6, 12]. In the monochromatic
matching version, if we can choose which pair of segments to add in a flip,
then $\mathbf{d}_{\texttt{MM}}(n)=\mathcal{O}(n^{2})$ [8]. For all remaining
cases, the best bounds known are $\mathbf{d}(n)=\Omega(n)$ and
$\mathbf{d}(n)=\mathcal{O}(n^{3})$.

It is also possible to relax the flip definition to all operations that
replace two segments by two others with the same four endpoints, whether they
cross or not [4, 5, 7, 9, 16, 31]. This definition has also been generalized
to multigraphs with the same degree sequence [18, 19, 21].

In the context of triangulations, a flip consists of removing one segment and
adding another one while preserving a triangulation. Reconfiguration problems
for triangulations are also widely studied [1, 20, 22, 23, 25, 27].

###  1.2 Definitions

Consider a set of points $P$. We say that two segments
$s_{1},s_{2}\in\binom{P}{2}$ _cross_ if they intersect in exactly one point
which is not an endpoint of either $s_{1}$ or $s_{2}$. Furthermore, a line
$\ell$ and a segment $s$ _cross_ if they intersect in exactly one point that
is not an endpoint of $s$.

Let $s_{1},s_{1}^{\prime},s_{2},s_{2}^{\prime}$ be four segments of
$\binom{P}{2}$ forming a cycle with $s_{1},s_{2}$ crossing. We define a _flip_
$f=s_{1},s_{2}\twoheadrightarrow s_{1}^{\prime},s_{2}^{\prime}$ as the
function that maps any set (or multiset) of segments $M$ containing the two
crossing segments $s_{1}$ and $s_{2}$ to
$f(M)=M\cup\\{s_{1}^{\prime},s_{2}^{\prime}\\}\setminus\\{s_{1},s_{2}\\}$
provided that $f(M)$ satisfies the property required by the version of the
problem in question (being a monochromatic matching, a red-blue matching, a
TSP tour…). This leads to the most general version of the problem, called the
_multigraph_ version. We note that a flip preserves the degree of every point.
However, a flip may not preserve the multiplicity of a segment, which is why,
in certain versions, we must consider multisets and multigraphs and not just
sets and graphs.

A _flip sequence_ of _length_ $m$ is a sequence of flips $f_{1},\ldots,f_{m}$
with a corresponding sequence of (multi-)sets of segments $M_{0},\ldots,M_{m}$
such that $M_{i}=f_{i}(M_{i-1})$ for $i=1,\ldots,m$. Unless mentioned
otherwise, we assume general position for the points in $P$ (no three
collinear points).

Given a property $\Pi$ over a multiset of $n$ line segments, we define
$\mathbf{D}_{\Pi}(n)$ as the maximum length of a flip sequence such that every
multiset of $n$ segments in the sequence satisfies property $\Pi$. We consider
the following properties $\Pi$: TSP for Hamiltonian cycle, RB for red-blue
matching, MM for monochromatic matching, and G for multigraph. Notice that if
a property $\Pi$ is stronger than a property $\Pi^{\prime}$, then
$\mathbf{D}_{\Pi}(n)\leq\mathbf{D}_{\Pi^{\prime}}(n)$.

##  2 Reductions

In this section, we provide a series of inequalities relating the different
versions of $\mathbf{D}(n)$. We show that all different versions of
$\mathbf{D}(n)$ have the same asymptotic behavior.

######  Theorem 2.1.

For all positive integer $n$, we have the following relations

$\displaystyle\mathbf{D}_{\mathtt{MM}}(n)$
$\displaystyle=\mathbf{D}_{\mathtt{G}}(n),$ (1) $\displaystyle
2\mathbf{D}_{\mathtt{MM}}(n)$
$\displaystyle\leq\mathbf{D}_{\mathtt{RB}}(2n)~{}\leq\mathbf{D}_{\mathtt{MM}}(2n),$
(2) $\displaystyle 2\mathbf{D}_{\mathtt{MM}}(n)$
$\displaystyle\leq\mathbf{D}_{\mathtt{TSP}}(3n)\leq\mathbf{D}_{\mathtt{MM}}(3n).$
(3)

###### Proof.

Equality 1 can be rewritten
$\mathbf{D}_{\mathtt{G}}(n)\leq\mathbf{D}_{\mathtt{MM}}(n)\leq\mathbf{D}_{\mathtt{G}}(n)$.
Hence, we have to prove six inequalities. The right-side inequalities are
immediate, since the left-side property is stronger than the right-side
property (using G instead of MM for inequality 3).

The proofs of the remaining inequalities follow the same structure: given a
flip sequence of the left-side version, we build a flip sequence of the right-
side version, having similar length and number of points.

We first prove the inequality
$\mathbf{D}_{\mathtt{G}}(n)\leq\mathbf{D}_{\mathtt{MM}}(n)$. A point of degree
$\delta$ larger than $1$ can be replicated as $\delta$ points that are
arbitrarily close to each other in order to produce a matching of $2n$ points.
This replication preserves the crossing pairs of segments (possibly creating
new crossings). Thus, for any flip sequence in the multigraph version, there
exists a flip sequence in the monochromatic matching version of equal length,
yielding $\mathbf{D}_{\mathtt{G}}(n)\leq\mathbf{D}_{\mathtt{MM}}(n)$.

(a)  (b)

Figure 2: (a) Two red-blue flips to simulate a monochromatic flip. (b) Two TSP
flips to simulate a monochromatic flip.

The left inequality of (2) is obtained by duplicating the monochromatic points
of the matching $M$ into two arbitrarily close points, one red and the other
blue. Then each segment of $M$ is also duplicated into two red-blue segments.
We obtain a bichromatic matching $M^{\prime}$ with $2n$ segments. A crossing
in $M$ corresponds to four crossings in $M^{\prime}$. Flipping this crossing
in $M$ amounts to choose which of the two possible pairs of segments replaces
the crossing pair. It is simulated by flipping the two crossings in
$M^{\prime}$ such that the resulting pair of double segments corresponds to
the resulting pair of segments of the initial flip. These two crossings always
exist and it is always possible to flip them one after the other as they
involve disjoint pairs of segments. Fig. 2(a) shows this construction. A
sequence of $m$ flips on $M$ provides a sequence of $2m$ flips on
$M^{\prime}$. Hence,
$2\mathbf{D}_{\mathtt{MM}}(n)\leq\mathbf{D}_{\mathtt{RB}}(2n)$.

To prove the left inequality of (3), we start from a red-blue matching $M$
with $2n$ points and $n$ segments and build a tour $T$ with $3n$ points and
$3n$ segments. We then show that the flip sequence of length $m$ on $M$
provides a flip sequence of length $2m$ on $T$. We build $T$ in the following
way. Given a red-blue segment $rb\in M$, the red point $r$ is duplicated in
two arbitrarily close points $r$ and $r^{\prime}$ which are adjacent to $b$ in
$T$. We still need to connect the points $r$ and $r^{\prime}$ in order to
obtain a tour $T$. We define $T$ as the tour
$r_{1},b_{1},r^{\prime}_{1},\ldots,r_{i},b_{i},r^{\prime}_{i},\ldots,r_{n},b_{n},r^{\prime}_{n}\ldots$
where $r_{i}$ is matched to $b_{i}$ in $M$ (Fig. 2(b)).

We now show that a flip sequence of $M$ with length $m$ provides a flip
sequence of $T$ with length $2m$. For a flip
$r_{i}b_{i},r_{j}b_{j}\twoheadrightarrow r_{i}b_{j},r_{j}b_{i}$ on $M$, we
perform two successive flips $r_{i}b_{i},r^{\prime}_{j}b_{j}\twoheadrightarrow
r_{i}b_{j},r^{\prime}_{j}b_{i}$ and
$r^{\prime}_{i}b_{i},r_{j}b_{j}\twoheadrightarrow
r^{\prime}_{i}b_{j},r_{j}b_{i}$ on $T$.

The tour then becomes
$r_{1},b_{1},r^{\prime}_{1},\ldots,r_{i},b_{j},r^{\prime}_{i},\ldots,r_{j},b_{i},r^{\prime}_{j},\ldots,r_{n},b_{n},r^{\prime}_{n},\ldots$
on which we can apply the next flips in the same way. Hence,
$2\mathbf{D}_{\mathtt{MM}}(n)\leq\mathbf{D}_{\mathtt{TSP}}(3n)$, concluding
the proof. ∎

##  3 Near Convex Sets

In this section, we bridge the gap between the $\mathcal{O}(n^{2})$ bound on
the length of flip sequences for a set $P$ of points in convex position and
the $\mathcal{O}(n^{3})$ bound for $P$ in general position. We prove the
following theorem in the monochromatic matching version; the translations to
the other versions follows from the reductions from Section 2, noticing that
all reductions preserve the number of points in non-convex position up to
constant factors.

######  Theorem 3.1.

In the monochromatic matching version with $n$ segments, if all except $t$
points of $P$ are in convex position, then the length of a flip sequence is
$\mathcal{O}(tn^{2})$.

###### Proof.

The proof strategy is to combine the potential $\Phi_{X}$ used in the convex
case with the potential $\Phi_{L}$ used in the general case. Given a matching
$M$, the potential $\Phi_{X}(M)$ is defined as the number of crossing pairs of
segments in $M$. Since there are $n$ segments in $M$,
$\Phi_{X}(M)\leq\binom{n}{2}=\mathcal{O}(n^{2})$. Unfortunately, with points
in non-convex position, a flip $f$ might _increase_ $\Phi_{X}$, i.e.
$\Phi_{X}(f(M))\geq\Phi_{X}(M)$ (as shown in Fig. 1).

The potential $\Phi_{L}$ is derived from the line potential introduced in [30]
but instead of using the set of all the $\mathcal{O}(n^{2})$ lines through two
points of $P$, we use a subset of $\mathcal{O}(tn)$ lines in order to take
into account that only $t$ points are in non-convex position. More precisely,
let the potential $\Phi_{\ell}(M)$ of a line $\ell$ be the number of segments
of $M$ crossing $\ell$. Note that $\Phi_{\ell}(M)\leq n$. The potential
$\Phi_{L}(M)$ is then defined as follows: $\Phi_{L}(M)=\sum_{\ell\in
L}\Phi_{\ell}(M)$.

We now define the set of lines $L$ as the union of $L_{1}$ and $L_{2}$,
defined hereafter. Let $C$ be the subset containing the $2n-t$ points of $P$
which are in convex position. Let $L_{1}$ be the set of the $\mathcal{O}(tn)$
lines through two points of $P$, at least one of which is not in $C$. Let
$L_{2}$ be the set of the $\mathcal{O}(n)$ lines through two points of $C$
which are consecutive on the convex hull boundary of $C$.

Let the potential $\Phi(M)=\Phi_{X}(M)+\Phi_{L}(M)$. We have the following
bounds: $0\leq\Phi(M)\leq\mathcal{O}(tn^{2})$. To complete the proof of
Theorem 3.1, we show that any flip decreases $\Phi$ by at least $1$ unit.

We consider an arbitrary flip $f=p_{1}p_{3},p_{2}p_{4}\twoheadrightarrow
p_{1}p_{4},p_{2}p_{3}$. Let $p_{x}$ be the point of intersection of
$p_{1}p_{3}$ and $p_{2}p_{4}$. It is shown in [12, 30] that $f$ never
increases the potential $\Phi_{\ell}$ of a line $\ell$. More precisely, we
have the following three cases:

  * •

The potential $\Phi_{\ell}$ decreases by $1$ unit if the line $\ell$ separates
the final segments $p_{1}p_{4}$ and $p_{2}p_{3}$ and exactly one of the four
flipped points belongs to $\ell$. We call these lines _$f$ -critical_ (Fig.
3(a)).

  * •

The potential $\Phi_{\ell}$ decreases by $2$ units if the line $\ell$ strictly
separates the final segments $p_{1}p_{4}$ and $p_{2}p_{3}$. We call these
lines _$f$ -dropping_ (Fig. 3(b)).

  * •

The potential $\Phi_{\ell}$ remains stable in the remaining cases.

Notice that, if a point $q$ lies in the triangle $p_{1}p_{x}p_{4}$, then the
two lines $qp_{1}$ and $qp_{4}$ are $f$-critical (Fig. 3(a)).

(a)  (b)

Figure 3: (a) An $f$-critical line $\ell$ for a flip
$f=p_{1}p_{3},p_{2}p_{4}\twoheadrightarrow p_{1}p_{4},p_{2}p_{3}$. This
situation corresponds to case (2a) with $\ell\in L_{1}$. (b) An $f$-dropping
line $\ell$. This situation corresponds to case (2b) with $\ell\in L_{2}$.

To prove that $\Phi$ decreases, we have the following two cases.

Case 1. If $\Phi_{X}$ decreases, as the other term $\Phi_{L}$ does not
increase, then their sum $\Phi$ decreases as desired.

Case 2. If not, then $\Phi_{X}$ increases by an integer $k$ with $0\leq k\leq
n-1$, and we know that there are $k+1$ new crossings after the flip $f$. Each
new crossing involves a distinct segment with one endpoint, say $q_{i}$
($0\leq i\leq k$), inside the non-simple polygon $p_{1},p_{4},p_{2},p_{3}$
(Fig. 3). Next, we show that each point $q\in\\{q_{0},\ldots,q_{k}\\}$ maps to
a distinct line in $L$ which is either $f$-dropping or $f$-critical, thus
proving that the potential $\Phi_{L}$ decreases by at least $k+1$ units.

We assume without loss of generality that $q$ lies in the triangle
$p_{1}p_{x}p_{4}$. We consider the two following cases.

Case 2a. If at least one among the points $q,p_{1},p_{4}$ is not in $C$, then
either $qp_{1}$ or $qp_{4}$ is an $f$-critical line $\ell\in L_{1}$ (Fig.
3(a)).

Case 2b. If not, then $q,p_{1},p_{4}$ are all in $C$, and the two lines
through $q$ in $L_{2}$ are both either $f$-dropping (the line $\ell$ in Fig.
3(b)) or $f$-critical (the line $qp_{4}$ in Fig. 3(b)). Consequently, there
are more lines $\ell\in L_{2}$ that are either $f$-dropping or $f$-critical
than there are such points $q\in C$ in the triangle $p_{1}p_{x}p_{4}$, and the
theorem follows. ∎

##  4 Distinct Flips

In this section, we prove the following theorem in the monochromatic matching
version, yet, the proof can easily be adapted to the other versions. We remark
that two flips are considered _distinct_ if the sets of four segments in the
flips are different.

######  Theorem 4.1.

In all versions with $n$ segments, the number of _distinct_ flips in any flip
sequence is $\mathcal{O}(n^{{8}/{3}})$.

The proof of Theorem 4.1 is based on a balancing argument from [15] and is
decomposed into two lemmas that consider a flip $f$ and two matchings $M$ and
$M^{\prime}=f(M)$. Similarly to [30], let $L$ be the set of lines defined by
all pairs of points in $\binom{P}{2}$. For a line $\ell\in L$, let
$\Phi_{\ell}(M)$ be the number of segments of $M$ crossed by $\ell$ and
$\Phi_{L}(M)=\sum_{\ell\in L}\Phi_{\ell}(M)$. Notice that
$\Phi(M)-\Phi(M^{\prime})$ depends only on the flip $f$ and not on $M$ or
$M^{\prime}$. The following lemma follows immediately from the fact that
$\Phi_{L}(M)$ takes integer values between $0$ and $\mathcal{O}(n^{3})$[30].

######  Lemma 4.2.

For any integer $k$, the number of flips $f$ in a flip sequence with
$\Phi(M)-\Phi(M^{\prime})\geq k$ is $\mathcal{O}(n^{3}/k)$.

Lemma 4.2 bounds the number of flips (distinct or not) that produce a large
potential drop in a flip sequence. Next, we bound the number of distinct flips
that produce a small potential drop. The bound considers all possible flips on
a fixed set of points and does not depend on a particular flip sequence.

######  Lemma 4.3.

For any integer $k$, the number of _distinct_ flips $f$ with
$\Phi(M)-\Phi(M^{\prime})<k$ is $\mathcal{O}(n^{2}k^{2})$.

###### Proof.

Let $F$ be the set of flips with $\Phi(M)-\Phi(M^{\prime})<k$ where
$M^{\prime}=f(M)$. We need to show that $|F|=\mathcal{O}(n^{2}k^{2})$.
Consider a flip $f=p_{1}p_{3},p_{2}p_{4}\twoheadrightarrow
p_{1}p_{4},p_{2}p_{3}$ in $F$. Next, we show that there are at most $4k^{2}$
such flips with a fixed final segment $p_{1}p_{4}$. Since there are
$\mathcal{O}(n^{2})$ possible values for $p_{1}p_{4}$, the lemma follows. We
show only that there are at most $2k$ possible values for $p_{3}$. The proof
that there are at most $2k$ possible values for $p_{2}$ is analogous.

Figure 4: Illustration for the proof of Lemma 4.3.

We sweep the points in $P\setminus\\{p_{4}\\}$ by angle from the ray
$p_{1}p_{4}$. As shown in Figure 4, let $q_{1},\ldots,q_{k}$ be the first $k$
points produced by this sweep in one direction, $q_{-1}\ldots,q_{-k}$ in the
other direction and $Q=\\{q_{-k}\ldots,q_{-1},q_{1},\ldots,q_{k}\\}$. To
conclude the proof, we show that $p_{3}$ must be in $Q$. Suppose $p_{3}\notin
Q$ for the sake of a contradiction and assume without loss of generality that
$p_{3}$ is on the side of $q_{i}$ with positive $i$. Then, consider the lines
$L^{\prime}=\\{p_{1}q_{1},\ldots,p_{1}q_{k}\\}$. Notice that
$L^{\prime}\subseteq L$, $|L^{\prime}|=k$, and for each $\ell\in L^{\prime}$
we have $\Phi_{\ell}(M)>\Phi_{\ell}(M^{\prime})$, which contradicts the
hypothesis that $\Phi(M)-\Phi(M^{\prime})<k$. ∎

Theorem 4.1 is a consequence of Lemmas 4.2 and 4.3 with $k=n^{{1}/{3}}$.

##  5 Conclusion and Open Problems

In Section 2, we showed a relationship among several different bounds on the
maximum number of flips for a set of $n$ line segments. This result shows how
upper bounds to the monochromatic matching version can be easily transferred
to different versions. But they can also be applied to transfer lower bounds
among different versions. For example, the lower bound of
$\frac{3}{2}\binom{n}{2}-\frac{n}{4}$ for the red-blue matching case [12]
implies a lower bound of $\frac{1}{3}\binom{n}{2}-\frac{n}{2}$ for TSP. It is
not clear if the constants in the TSP lower bound may be improved, perhaps by
a more direct approach (or perhaps the lower bounds are not even
asymptotically tight). However, we showed that all these versions are related
by constant factors.

We can also use the results from Section 2 to convert the bounds from Section
3 to the general multigraph version, and hence to spanning trees and other
types of graphs. In this case, the number $t$ of points in non-convex position
needs to be replaced by the sum of the degrees of the points in non-convex
position. If the graphs are dense, or have non-constant degree, we do not know
of any non-trivial lower bounds or better upper bounds.

Another key property that we did not consider in this paper is the length
$\mathbf{d}(n)$ of the shortest flip sequence to untangle any set of $n$
segments. In general, we only know that $\mathbf{d}(n)=\Omega(n)$ and
$\mathbf{d}(n)\leq\mathbf{D}(n)=\mathcal{O}(n^{3})$, for all versions. Whether
similar reductions are possible is an elusive question. Furthermore, if the
$n$ points are in convex position, then $\mathbf{d}_{TSP}(n)=\Theta(n)$ for
all versions. It is unclear if a transition in the case of $t$ points in non-
convex position is possible.

The result of Theorem 4.1 is based on the $\mathcal{O}(n^{2}k^{2})$ bound from
Lemma 4.3. A better analysis of the dual arrangement could potentially improve
this bound, perhaps to $\mathcal{O}(n^{2}k)$.

The main open question, though, is whether the $\mathcal{O}(n^{3})$ bound to
both $\mathbf{D}(n)$ and $\mathbf{d}(n)$ can be improved for points in general
position. The $\mathcal{O}(n^{8/3})$ bound on the number of distinct flips
presented in Section 4 is a hopeful step in this direction, at least for
$\mathbf{d}(n)$. We were not able to find a set of line segments that requires
the same pair of segments to be flipped twice in order to be untangled.

## References

  * [1] Oswin Aichholzer, Wolfgang Mulzer, and Alexander Pilz.  Flip distance between triangulations of a simple polygon is NP-complete.  Discrete & Computational Geometry, 54(2):368–389, 2015.
  * [2] David L Applegate, Robert E Bixby, Vašek Chvátal, and William J Cook.  The traveling salesman problem.  In The Traveling Salesman Problem. Princeton university press, 2011\.
  * [3] Sanjeev Arora.  Polynomial time approximation schemes for Euclidean TSP and other geometric problems.  In 37th Conference on Foundations of Computer Science, pages 2–11, 1996.
  * [4] Sergey Bereg and Hiro Ito.  Transforming graphs with the same degree sequence.  In Computational Geometry and Graph Theory, pages 25–32, 2008.
  * [5] Sergey Bereg and Hiro Ito.  Transforming graphs with the same graphic sequence.  Journal of Information Processing, 25:627–633, 2017.
  * [6] Ahmad Biniaz, Anil Maheshwari, and Michiel Smid.  Flip distance to some plane configurations.  Computational Geometry, 81:12–21, 2019.  URL: https://arxiv.org/abs/1905.00791.
  * [7] Marthe Bonamy, Nicolas Bousquet, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Arnaud Mary, Moritz Mühlenthaler, and Kunihiro Wasa.  The perfect matching reconfiguration problem.  In 44th International Symposium on Mathematical Foundations of Computer Science, volume 138 of LIPIcs, pages 80:1–80:14, 2019.
  * [8] Édouard Bonnet and Tillmann Miltzow.  Flip distance to a non-crossing perfect matching.  arXiv, 1601.05989, 2016.  URL: http://arxiv.org/abs/1601.05989.
  * [9] Nicolas Bousquet and Alice Joffard.  Approximating shortest connected graph transformation for trees.  In Theory and Practice of Computer Science, pages 76–87, 2020.
  * [10] Maike Buchin and Bernhard Kilgus.  Fréchet distance between two point sets.  Computational Geometry, 102:101842, 2022.
  * [11] Miroslav Chlebík and Janka Chlebíková.  Approximation hardness of Travelling Salesman via weighted amplifiers.  In 25th International Computing and Combinatorics Conference, pages 115–127, 2019.
  * [12] Arun Kumar Das, Sandip Das, Guilherme D. da Fonseca, Yan Gerard, and Bastien Rivier.  Complexity results on untangling red-blue matchings.  In 15th Latin American Theoretical Informatics Symposium (LATIN 2022), volume to appear of Lecture Notes in Computer Science, 2022.  URL: https://arxiv.org/abs/2202.11857.
  * [13] Donald Davendra.  Traveling salesman problem: Theory and applications.  BoD–Books on Demand, 2010.
  * [14] Matthias Englert, Heiko Röglin, and Berthold Vöcking.  Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP.  Algorithmica, 68(1):190–264, 2014.
  * [15] Paul Erdös, László Lovász, A Simmons, and Ernst G Straus.  Dissection graphs of planar point sets.  In A survey of combinatorial theory, pages 139–149. Elsevier, 1973\.
  * [16] Péter L Erdős, Zoltán Király, and István Miklós.  On the swap-distances of different realizations of a graphical degree sequence.  Combinatorics, Probability and Computing, 22(3):366–383, 2013.
  * [17] Gregory Gutin and Abraham P Punnen.  The traveling salesman problem and its variations, volume 12.  Springer Science & Business Media, 2006.
  * [18] Seifollah Louis Hakimi.  On realizability of a set of integers as degrees of the vertices of a linear graph. I.  Journal of the Society for Industrial and Applied Mathematics, 10(3):496–506, 1962.
  * [19] Seifollah Louis Hakimi.  On realizability of a set of integers as degrees of the vertices of a linear graph II. uniqueness.  Journal of the Society for Industrial and Applied Mathematics, 11(1):135–147, 1963.
  * [20] Ferran Hurtado, Marc Noy, and Jorge Urrutia.  Flipping edges in triangulations.  Discrete & Computational Geometry, 22(3):333–346, 1999.
  * [21] Alice Joffard.  Graph domination and reconfiguration problems.  PhD thesis, Université Claude Bernard Lyon 1, 2020.
  * [22] Charles L Lawson.  Transforming triangulations.  Discrete Mathematics, 3(4):365–372, 1972.
  * [23] Anna Lubiw and Vinayak Pathak.  Flip distance between two triangulations of a point set is NP-complete.  Computational Geometry, 49:17–23, 2015.
  * [24] Joseph SB Mitchell.  Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric tsp, k-mst, and related problems.  SIAM Journal on computing, 28(4):1298–1309, 1999.
  * [25] Naomi Nishimura.  Introduction to reconfiguration.  Algorithms, 11(4), 2018.
  * [26] Yoshiaki Oda and Mamoru Watanabe.  The number of flips required to obtain non-crossing convex cycles.  In Kyoto International Conference on Computational Geometry and Graph Theory, pages 155–165, 2007.
  * [27] Alexander Pilz.  Flip distance between triangulations of a planar point set is apx-hard.  Computational Geometry, 47(5):589–604, 2014.
  * [28] Satish B Rao and Warren D Smith.  Approximating geometrical graphs via “spanners” and “banyans”.  In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 540–550, 1998.
  * [29] Jan van den Heuvel.  The complexity of change.  Surveys in Combinatorics, 409:127–160, 2013.
  * [30] Jan van Leeuwen.  Untangling a traveling salesman tour in the plane.  In 7th Workshop on Graph-Theoretic Concepts in Computer Science, 1981.
  * [31] Todd G Will.  Switching distance between graphs with the same degrees.  SIAM Journal on Discrete Mathematics, 12(3):298–306, 1999.
  * [32] Ro-Yu Wu, Jou-Ming Chang, and Jia-Huei Lin.  On the maximum switching number to obtain non-crossing convex cycles.  In 26th Workshop on Combinatorial Mathematics and Computation Theory, pages 266–273, 2009.