# Does gravitational wave assist vacuum steering and Bell nonlocality?

Shu-Min<EMAIL_ADDRESS>Rui-Di Wang1, Xiao-Li Huang1222
<EMAIL_ADDRESS>, Zejun Wang2<EMAIL_ADDRESS>(corresponding author) 1 Department of Physics, Liaoning Normal University,
Dalian 116029, China
2 Department of Physics, Changzhi University, Changzhi, 046011, China

###### Abstract

We study quantum steering and Bell nonlocality harvested by the local
interaction of two Unruh-DeWitt detectors with the vacuum massless scalar
field, both in the presence of gravitational waves and in Minkowski spacetime.
It is shown that quantum steerability under the influence of gravitational
waves can be greater than or less than quantum steerability in Minkowski
spacetime, which means that the gravitational waves can amplify or degrade the
harvested steering. In particular, a resonance effect occurs when the energy
gap of the detector is tuned to the frequency of the gravitational wave. We
also find that the harvesting-achievable separation range of vacuum steering
can be expanded or reduced by the presence of gravitational waves, which
depends on the energy gap, the gravitational wave frequency, and the duration
of the gravitational wave action. It is interesting to note that two detector
systems that satisfy the Bell inequality, regardless of the existence of
gravitational waves, indicating that steering harvesting cannot be considered
to be nonlocal.

###### pacs:

04.70.Dy, 03.65.Ud,04.62.+v

##  I Introduction

Einstein-Podolsky-Rosen (EPR) steering is a quantum phenomenon that describes
the control of the state of one entangled subsystem by an observer taking a
local measurement of the other, discovered by Schrödinger in 1935 L0-1 ; L0-2
; L1 . Later, Einstein, Podolsky, and Rosen (EPR) studied the concept of
quantum steering in their famous paper L2 , and it is seen as a central
concept of the EPR paradox L3 . Apart from that, Bell established the Bell
inequality, which can be used to determine whether quantum nonlocality exists
L4 . Even if two quantum systems are spatially far apart, they cannot be
considered nonlocal when the Bell inequality is satisfied. Conversely, if the
Bell inequality is violated, then the two quantum systems are said to be
nonlocal L5 . Quantum steerability is a form of medial nonlocal correlation
between entanglement and Bell nonlocality L6 . Entanglement is weaker than
quantum steering, and Bell nonlocality is stronger than quantum steering L7 .
Unlike entanglement and Bell nonlocality, quantum steering is characterized by
asymmetry L8 . It has aroused the interest in both theoretically and
experimentally, and has received some confirmation L10 ; L11 ; L12 ; L16 ; L21
; L25 . It was realized that quantum steering is an important resource for
processing quantum information tasks, such as subchannel discrimination,
randomness generation, one-sided device-independent quantum key distribution
and quantum teleportation L27 ; L30 ; L33 ; L34 . Like quantum steering,
quantum nonlocality is also an important quantum resource, which has been
applied to the many fields of communication complexity, quantum cryptography
and randomness generation L35 ; L36 ; L37 ; L38 ; L39 ; L40 .

It is well known that the study of quantum information is closely related to
the nature of the quantum vacuum. The vacuum state of any quantum field in
turn depends on the structure of spacetime. We can obtain understanding of the
quantum vacuum and its response to the structure of spacetime by coupling the
quantum field to the first-quantized particle detectors. At present, it is
shown that the vacuum state of the quantum field has non-local correlations,
and these correlations can be harvested using Unruh-DeWitt (UDW) detectors
L60-4 ; L60-5 ; L42 ; L44 ; L45 . In this way, vacuum correlations can be
transferred to the detectors in the form of mutual information, quantum
discord, and entanglement. The captured entanglement can be further refined
into Bell pairs L46 , suggesting that the vacuum is in principle a quantum
resource for quantum information tasks. This process is called entanglement
harvesting L47 ; L48 ; L49 ; L50 ; L51 ; L52 ; L53 ; L54 ; L55 ; L56 ; L57 ;
L58 ; L59 ; L60 ; L60-1 ; L60-2 ; L60-3 . However, quantum steering and Bell
nonlocality from the vacuum harvesting have not been studied yet in the
context of curved spacetime. Since quantum steering and Bell nonlocality are
very important quantum resources, it is necessary to study them from the
vacuum harvesting under the influence of gravitational waves. This is one of
the motivations for our research. Another motivation is to obtain relevant
information of gravitational waves through quantum steering harvesting and
Bell nonlocality harvesting.

In this paper, we consider this issue, performing a complete investigation of
gravitational waves-assisted steering harvesting phenomenon. In other words,
we study quantum steering harvested from the vacuum under the influence of
gravitational waves and in Minkowski spacetime. We emphasize that a panoramic
understanding of gravitational waves-assisted steering harvesting should
include the following two aspects. One is whether steering harvesting can
indeed be assisted by gravitational waves in terms of the amount of steering
harvested; the other question is whether the achievable separation range for
steering harvesting between the detectors can be enlarged in comparison with
Minkowski spacetime. As we will demonstrate, the presence of gravitational
waves is actually a mixed blessing for steering harvesting: In some cases, it
may contribute to harvesting, while in other cases it may degrade harvesting.
Specifically, the presence of gravitational waves can shorten or widen the
harvesting-achievable separation range, depending on the energy gap, the
gravitational wave frequency, and the duration of the gravitational wave
action. In addition, we also study vacuum Bell nonlocality of two UDW
detectors and find that Bell nonlocality cannot be extracted from the vacuum.

The structure of the paper is as follows. In Sec. II, we briefly introduce
quantification of quantum steering and the Clauser-Horne-Shimony-Holt (CHSH)
inequality. In Sec. III, we discuss scalar field theory and UDW detectors
model in the background of gravitational waves. In Sec. IV, we study vacuum
steering and Bell nonlocality of two UDW detectors under the influence of
gravitational waves. The last section is devoted to a brief conclusion.

##  II Quantification of quantum steering and CHSH inequality

Quantum steering represents a distinctive form of quantum correlation. Within
a prototypical quantum steering framework, our focus is on two particles that
jointly inhabit a bipartite quantum state, named Alice and Bob. It should be
noted that the concurrence serves as an effective metric for discerning the
quantum entanglement in bipartite states L61 . Here, we consider the density
matrix of the X-state $\rho_{AB}$ as

$\displaystyle\rho_{AB}=\left(\\!\\!\begin{array}[]{cccccccc}\rho_{11}&0&0&\rho_{14}\\\
0&\rho_{22}&\rho_{23}&0\\\ 0&\rho_{32}&\rho_{33}&0\\\
\rho_{41}&0&0&\rho_{44}\\\ \end{array}\\!\\!\right),$ (5)

where the real elements of the matrix satisfy $\rho_{ij}=\rho_{ji}$. Then, the
concurrence can be expressed as L63

$\displaystyle
C(\rho_{AB})=2\max\\{|\rho_{14}|-\sqrt{\rho_{22}\rho_{33}},|\rho_{23}|-\sqrt{\rho_{11}\rho_{44}}\\}.$
(6)

Subsequently, for the X-state $\rho_{AB}$ shared by Alice and Bob, the
steering from Bob to Alice can be sighted if the density matrix $\tau_{AB}$
defined as L64 ; L65

$\displaystyle\tau_{AB}=\frac{\rho_{AB}}{\sqrt{3}}+\frac{3-\sqrt{3}}{3}(\rho_{A}\otimes\frac{I}{2}),$
(7)

is entangled. Here, $\rho_{A}=Tr_{B}(\rho_{AB})$ is the reduced density matrix
of Alice, and $I$ represents the two-dimensional identity matrix. Similarly,
the corresponding steering from Alice to Bob can be demonstrated if the state
$\tau_{BA}$ defined as

$\displaystyle\tau_{BA}=\frac{\rho_{AB}}{\sqrt{3}}+\frac{3-\sqrt{3}}{3}(\frac{I}{2}\otimes\rho_{B})$
(8)

is entangled, where $\rho_{B}=Tr_{A}(\rho_{AB})$ is Bob’s reduced density
matrix.

Employing Eqs.(5) and (7), the matrix $\tau_{AB}$ of Eq.(5) can be
specifically shown as

$\displaystyle\tau^{x}_{AB}=\left(\\!\\!\begin{array}[]{cccccccc}\frac{\sqrt{3}}{3}\rho_{11}+m&0&0&\frac{\sqrt{3}}{3}\rho_{14}\\\
0&\frac{\sqrt{3}}{3}\rho_{22}+m&\frac{\sqrt{3}}{3}\rho_{23}&0\\\
0&\frac{\sqrt{3}}{3}\rho_{32}&\frac{\sqrt{3}}{3}\rho_{33}+n&0\\\
\frac{\sqrt{3}}{3}\rho_{41}&0&0&\frac{\sqrt{3}}{3}\rho_{44}+n\\\
\end{array}\\!\\!\right),$ (13)

with $m=\frac{(3-\sqrt{3})}{6}(\rho_{11}+\rho_{22})$ and
$n=\frac{(3-\sqrt{3})}{6}(\rho_{33}+\rho_{44})$. By using Eq.(6), the state
$\tau_{AB}$ is entangled if one of the following inequalities,

$\displaystyle|\rho_{14}|^{2}>G_{a}-G_{b},$ (14)

or

$\displaystyle|\rho_{23}|^{2}>G_{c}-G_{b},$ (15)

is satisfied, where

$\displaystyle
G_{a}=\frac{2-\sqrt{3}}{2}\rho_{11}\rho_{44}+\frac{2+\sqrt{3}}{2}\rho_{22}\rho_{33}+\frac{1}{4}(\rho_{11}+\rho_{44})(\rho_{22}+\rho_{33}),$
$\displaystyle G_{b}=\frac{1}{4}(\rho_{11}-\rho_{44})(\rho_{22}-\rho_{33}),$
$\displaystyle
G_{c}=\frac{2+\sqrt{3}}{2}\rho_{11}\rho_{44}+\frac{2-\sqrt{3}}{2}\rho_{22}\rho_{33}+\frac{1}{4}(\rho_{11}+\rho_{44})(\rho_{22}+\rho_{33}).$
(16)

The steering from Alice to Bob can be observed similarly to the steering from
Bob to Alice, by examining one of the inequalities,

$\displaystyle|\rho_{14}|^{2}>G_{a}+G_{b},$ (17)

or

$\displaystyle|\rho_{23}|^{2}>G_{c}+G_{b}.$ (18)

According to the above inequalities, we can quantify the steering from Bob to
Alice and the steering from Alice to Bob

$\displaystyle T^{B\rightarrow
A}=\max\\{0,\frac{8}{\sqrt{3}}(|\rho_{14}|^{2}-G_{a}+G_{b}),\frac{8}{\sqrt{3}}(|\rho_{23}|^{2}-G_{c}+G_{b})\\},$
(19)

and

$\displaystyle T^{A\rightarrow
B}=\max\\{0,\frac{8}{\sqrt{3}}(|\rho_{14}|^{2}-G_{a}-G_{b}),\frac{8}{\sqrt{3}}(|\rho_{23}|^{2}-G_{c}-G_{b})\\}.$
(20)

Note that the steerability of the maximally entangled state is guaranteed to
be 1 by the factor $\frac{8}{\sqrt{3}}$.

Bell nonlocality also constitutes a unique manifestation of quantum
correlation, which is determined by Bell inequality. Then, we employ the CHSH
inequality, an inequality that holds for two qubits, to test local realist
theories. The Bell operator is the key element for the CHSH inequality and is
defined as L66

$\displaystyle
B_{CHSH}=\mathbf{a}\cdot\mathbf{\sigma}\otimes(\mathbf{b}+\mathbf{b^{\prime}})\cdot\mathbf{\sigma}+\mathbf{a^{\prime}}\cdot\mathbf{\sigma}\otimes(\mathbf{b}-\mathbf{b^{\prime}})\cdot\mathbf{\sigma},$
(21)

where $\mathbf{a},\mathbf{a^{\prime}},\mathbf{b}$, and $\mathbf{b^{\prime}}$
represent unit vectors in $\mathbb{R}^{3}$, and
$\mathbf{\sigma}=(\mathbf{\sigma}_{1},\mathbf{\sigma}_{2},\mathbf{\sigma}_{3})$
is the vector of Pauli matrices. The expression of the CHSH inequality we
mentioned for any bipartite mixed state $\rho$ is

$\displaystyle B(\rho)=|Tr(\rho B_{CHSH})|\leq 2.$ (22)

Clearly, the violation of the inequality indicates the presence of Bell
nonlocality with respect to the underlying state. For a general two-qubit
state, a bound for the maximum possible violation of Eq.(22) is given in
reference L66-1 . We need to determine the maximal Bell signal $B(\rho)$,
which in the case of two-qubit systems $\rho$, can be considered equivalent to

$\displaystyle B(\rho)=2\sqrt{\max_{i<j}(F_{i}+F_{j})},$ (23)

where $F_{i}$ and $F_{j}$ are the two largest eigenvalues of
$U(\rho)=T^{T}_{\rho}T_{\rho}$, and $T=(t_{ij})$ denotes the correlation
matrix with $t_{ij}=Tr[\rho\sigma_{i}\otimes\sigma_{j}]$. For two-qubit
X-state, the corresponding matrix $U(\rho)$ has three eigenvalues

$\displaystyle F_{1}=4(|\rho_{14}|+|\rho_{23}|)^{2},$ $\displaystyle
F_{2}=4(|\rho_{14}|-|\rho_{23}|)^{2},$ $\displaystyle
F_{3}=(|\rho_{11}|-|\rho_{22}|-|\rho_{33}|+|\rho_{44}|)^{2}.$ (24)

Since $F_{1}$ is larger than $F_{2}$, the maximal Bell signal reads

$\displaystyle B(\rho_{x})=\max\\{B_{1},B_{2}\\},$ (25)

with $B_{1}=2\sqrt{F_{1}+F_{2}}$ and $B_{2}=2\sqrt{F_{1}+F_{3}}$ L67 ; L68 .
Therefore, we will use Eqs.(22), (23), and (25) to judge whether quantum
steering is nonlocal in the context of gravitational waves.

##  III Unruh-DeWitt model in the background of gravitational waves

In the context of a gravitational wave propagating along the z-direction, the
pertinent description is encapsulated within the line element as follows:

$\displaystyle ds^{2}$ $\displaystyle=$ $\displaystyle-
dt^{2}+dz^{2}+(1+A\cos\left[\omega(t-z)\right])dx^{2}+(1-A\cos\left[\omega(t-z)\right])dy^{2}$
(26) $\displaystyle=-dudv+(1+A\cos\omega u)dx^{2}+(1-A\cos\omega u)dy^{2}.$

Here, we introduce light cone coordinates, denoted as $u:=t-z$ and $v:=t+z$,
defined based on Minkowski coordinates $(t,x,y,z)$. This spacetime solution
corresponds to the linearized field equation and is effective for the leading
order of $A\ll 1$. Within this spacetime framework, we examine a massless
scalar field $\Phi(x)$ that satisfies to the Klein-Gordon equation at a given
spacetime point

$\displaystyle\Box\phi(\mathsf{x})=0,$ (27)

where the d’Alembertian operator $\Box$ is related to the Eq.(26). Solving
this equation in light-cone coordinates $x=(u,v,x,y)$ produces a complete set
of solutions L69

$\displaystyle u_{\vec{k}}(\mathsf{x})=$
$\displaystyle\frac{\gamma^{-1}(u)}{\sqrt{2k_{-}}(2\pi)^{\frac{3}{2}}}e^{ik_{a}x^{a}-ik_{-}v-\frac{i}{4k_{-}}\int_{0}^{u}du\,(g^{ab}k_{a}k_{b})},$
(28)

where the constants $k_{-}$ and $k_{a}$ emerge as separability constants upon
solving Eq.(28) in the light-cone coordinates, the indices $a$ and $b$ run
over $\\{x,y\\}$, and $\gamma^{-1}(u)=[\det g_{ab}(u)]^{\frac{1}{4}}$. We
interpret the mode functions in Eq.(28) as delineating the perturbation to the
Minkowski vacuum caused by the gravitational wave.

Through detailed calculations, we can obtain the vacuum Wightman function as

$\displaystyle W(\mathsf{x},\mathsf{x}^{\prime})$ $\displaystyle:=$
$\displaystyle\langle
0|\phi(\mathsf{x})\phi(\mathsf{x}^{\prime})|0\rangle=\int
d\mathsf{k}\,u_{\mathsf{k}}(\mathsf{x})u_{\mathsf{k}}^{*}(\mathsf{x}^{\prime})=W_{\mathcal{M}}(\mathsf{x},\mathsf{x}^{\prime})+W_{\rm
GW}(\mathsf{x},\mathsf{x}^{\prime}).$ (29)

Here, $W_{\mathcal{M}}(\mathsf{x},\mathsf{x}^{\prime})$ denotes the Minkowski
Wightman function, independent of the gravitational wave, in light-cone
coordinates, and $W_{\rm GW}(\mathsf{x},\mathsf{x}^{\prime})$ represents the
first-order modification of the Minkowski Wightman function with respect to
the amplitude of the gravitational wave L70 . Their specific expressions,
respectively, are

$\displaystyle W_{\mathcal{M}}(\mathsf{x},\mathsf{x}^{\prime})$
$\displaystyle=$ $\displaystyle\\!\frac{1}{4\pi i\Delta
u}\delta\left(\frac{\sigma_{\mathcal{M}}(\mathsf{x},\mathsf{x}^{\prime})}{\Delta
u}\right)+\frac{1}{4\pi^{2}\sigma_{\mathcal{M}}(\mathsf{x},\mathsf{x}^{\prime})},$
(30)

and

$\displaystyle W_{\rm GW}(\mathsf{x},\mathsf{x}^{\prime})$ $\displaystyle=$
$\displaystyle\\!-\tfrac{A}{4\pi^{2}}\rm{sinc}\left(\tfrac{\omega}{2}\Delta
u\right)\cos\left(\tfrac{\omega}{2}[u+u^{\prime}]\right)\times\\!\tfrac{\Delta
x^{2}-\Delta y^{2}}{\Delta
u^{2}}\\!\left[i\pi\delta^{\prime}\\!\left(\tfrac{\sigma_{\rm\mathcal{M}}(\mathsf{x},\mathsf{x}^{\prime})}{\Delta
u}\right)\\!+\\!\tfrac{\Delta
u^{2}}{\sigma_{\mathcal{M}}^{2}(\mathsf{x},\mathsf{x}^{\prime})}\right]\\!,$
(31)

where $\Delta\mathsf{x}^{\mu}:=\mathsf{x}^{\mu}-\mathsf{x}^{\prime\mu}$, and
$\sigma_{\mathcal{M}}(\mathsf{x},\mathsf{x}^{\prime}):=-\Delta u\Delta
v+\Delta x^{2}+\Delta y^{2}$ represents the geodesic distance between points
$x$ and $x^{\prime}$ in Minkowski space.

To experimentally investigate the impact of the gravitational wave on vacuum
steering and Bell nonlocality of a scalar field theory, we utilize two Unruh-
DeWitt detectors, labeled $A$ and $B$, with the ground state $|0_{D}\rangle$
and the excited state $|1_{D}\rangle(D\in\\{A,B\\})$, separated by the energy
gap 2$\Omega$. Two detectors interact locally with the scalar field
$\phi(\mathsf{x})$ along its trajectory $\mathsf{x}_{D}(t)$ of parametrized by
its proper time $t$. The Hamiltonian governing this interaction is

$\displaystyle H_{D}(t)$
$\displaystyle=\lambda\chi\\!\left(t\right)\Big{(}e^{i\Omega
t}\sigma^{+}+e^{-i\Omega
t}\sigma^{-}\Big{)}\otimes\phi\left[\mathsf{x}_{D}(t)\right],$ (32)

where $\chi(t)=\exp[-\frac{(t-t_{0})^{2}}{2\sigma^{2}}]$ is the switching
function of $t_{0}$ and $\sigma$, which correspond to the occurrence and
duration of the interaction, respectively, $\lambda$ is the coupling constant
and describes the strength of the interaction, and
$\sigma^{+}=|{1_{D}}\rangle\langle{0_{D}}|$ and
$\sigma^{-}=|{0_{D}}\rangle\langle{1_{D}}|$ denote SU(2) ladder operators
acting on the detector Hilbert space.

Initially, consider these detectors prepared as ($t\rightarrow-\infty$) in
their ground state $|{0}\rangle_{A}|{0}\rangle_{B}$, and the field state in a
suitably defined the vacuum state $|0\rangle$, ensuring that the combined
state of the detectors and the field is denoted as
$|{\Psi_{i}}\rangle=|{0}\rangle_{A}|{0}\rangle_{B}|{0}\rangle$. With the
interaction Hamiltonian of Eq.(32), the final state ($t\rightarrow\infty$) of
the detectors and field becomes
$|{\Psi_{f}}\rangle=\mathcal{T}e^{-i\int_{\mathbb{R}}dt\,\left[H_{A}(t)+H_{B}(t)\right]}|{\Psi_{i}}\rangle$,
where $H_{A}(t)$ and $H_{B}(t)$ are specified in Eq.(32), and $\mathcal{T}$
represents the time ordering operator. The reduced state of the detectors is
derived in the basis
$\\{|{0_{A}0_{B}}\rangle,|{0_{A}1_{B}}\rangle,|{1_{A}0_{B}}\rangle,|{1_{A}1_{B}}\rangle\\}$
by performing a trace operation over the field

$\displaystyle\rho_{AB}:=\rm{tr}_{\phi}(|\Psi_{f}\rangle\langle\Psi_{f}|)=\begin{pmatrix}1-2P&0&0&X\\\
0&P&C&0\\\ 0&C^{*}&P&0\\\
X^{*}&0&0&0\end{pmatrix}+\mathcal{O}\\!\left(\lambda^{4}\right).$ (33)

Here, the matrix elements $X$ and $C$ characterize nonclassical correlations
and are the sum of two terms: $X=X_{\mathcal{M}}+X_{\rm GW}$ and
$C=C_{\mathcal{M}}+C_{\rm GW}$. Obviously, $X_{\mathcal{M}}$ and
$C_{\mathcal{M}}$ correspond to the values of $X$ and $C$ when the detector is
in Minkowski space, $X_{\rm GW}$ and $C_{\rm GW}$ correspond to the
modifications of the matrix elements $X$ and $C$ resulting from the influence
of the gravitational wave. Besides, there is also a matrix element, the
transition probability $P$ that in the distant future ($t\rightarrow\infty$)
the detector will transition to the excited state $|1_{D}\rangle$, as a result
of the vacuum fluctuations and a limited interaction time.

In particular, consider the scenario where the detector is at rest relative to
the Minkowski coordinates introduced in Eq.(26), resulting in its trajectory
being a geodesic $\mathsf{x}_{D}(t)=(t,0,0,0)$. Due to the condition $\Delta
x^{2}=\Delta y^{2}=0$, the transition probability $P$ is not affected by
gravitational waves. It can also be asserted that a single detector is unable
to discern the existence of a gravitational wave. Thus, we can specifically
express $P$ as

$\displaystyle
P=\frac{\lambda^{2}}{4\pi}\left[e^{-\sigma^{2}\Omega^{2}}-\sqrt{\pi}\sigma\Omega\left(1-\rm{erf}[\sigma\Omega]\right)\right].$
(34)

To operationally probe vacuum steering and Bell nonlocality across spacetime
regions, we consider the trajectories of detectors $A$ and $B$, delineated in
Minkowski coordinates
$\mathsf{x}_{A}(t)=(t,0,0,0),\mathsf{x}_{B}(t)=(t,D,0,0)$. Consider that due
to the detectors interacting with the field for an approximate proper time
$\sigma$, detectors following these trajectories may be deemed approximately
spacelike separated during the interaction when $D>\sigma$ and timelike when
$D<\sigma$; $D$ denotes the average appropriate distance between the detectors
L70 . Combined with the Wightman function, the $X_{\mathcal{M}}$,
$C_{\mathcal{M}}$, $X_{\rm GW}$, and $C_{\rm GW}$ can be expressed as

$\displaystyle
X_{\mathcal{M}}:=i\frac{\sigma\lambda^{2}}{4D\sqrt{\pi}}e^{-\sigma^{2}\Omega^{2}-2i\Omega
t_{0}-\frac{D^{2}}{4\sigma^{2}}}\left[\rm{erf}\left(\frac{iD}{2\sigma}\right)-1\right]\\!,$
(35) $\displaystyle
C_{\mathcal{M}}:=\frac{\sigma\lambda^{2}}{4D\sqrt{\pi}}e^{-\frac{D^{2}}{4\sigma^{2}}}\times\left(\rm{Im}\left[e^{iD\Omega}\rm{erf}\left(i\frac{D}{2\sigma}+\sigma\Omega\right)\right]-\sin\Omega
D\right),$ (36) $\displaystyle
X_{\rm{GW}}:=\frac{A\sigma\lambda^{2}}{4D^{2}\pi^{3/2}}f(\omega,\Omega,\sigma,t_{0})\left(I_{1}+I_{2}\right),$
(37)

and

$\displaystyle
C_{\rm{GW}}:=-\frac{A\sigma\lambda^{2}}{4D^{2}\pi^{3/2}}e^{-\frac{\sigma^{2}\omega^{2}}{4}}\cos\left(\omega
t_{0}\right)\left(I_{3}+I_{4}\right),$ (38)

with

$\displaystyle
f(\omega,\Omega,\sigma,t_{0}):=e^{-\frac{\sigma^{2}}{4}(\omega-2\Omega)^{2}-it_{0}(\omega+2\Omega)}+e^{-\frac{\sigma^{2}}{4}(\omega+2\Omega)^{2}+it_{0}(\omega-2\Omega)}.$
(39)

The terms $I_{1}$ and $I_{2}$ are about $\omega$, $D$, and $\sigma$ of complex
functions, $I_{3}$ and $I_{4}$ are tanglesome functions of $\omega$, $D$,
$\sigma$, and $\Omega$. Their representations are as follows:

$\displaystyle I_{1}=i\frac{\pi
e^{-\frac{D^{2}}{4\sigma^{2}}}}{\omega}\left[\left(\frac{D^{2}}{4\sigma^{2}}+1\right)\sin\left(\tfrac{\omega}{2}D\right)-\frac{D\omega}{4}\cos\left(\tfrac{\omega}{2}D\right)\right],$
$\displaystyle
I_{2}=\frac{\pi}{\omega}\left(\rm{erf}\left(\frac{\sigma\omega}{2}\right)-e^{-\frac{D^{2}}{4\sigma^{2}}}\rm{Re}\left[e^{i\frac{\omega}{2}D}\left(1+\frac{D^{2}}{4\sigma^{2}}-i\frac{D\omega}{4}\right)\rm{erf}\left(\frac{\omega}{2}\sigma+\frac{i\rm{D}}{2\sigma}\right)\right]\right),$
$\displaystyle I_{3}=\frac{\pi
e^{-\frac{D^{2}}{4\sigma^{2}}}}{4\omega}\Bigg{[}\left(D\omega+2D\Omega\right)\sin\left(D\left[\frac{\omega}{2}+\Omega\right]\right)+\left(D\omega-2D\Omega\right)\sin\left(D\left[\frac{\omega}{2}-\Omega\right]\right)$
$\displaystyle+\left(\frac{D^{2}}{\sigma^{2}}+4\right)\left(\cos\left(D\left[\frac{\omega}{2}+\Omega\right]\right)-\cos\left(D\left[\frac{\omega}{2}-\Omega\right]\right)\right)\Bigg{]},$
$\displaystyle
I_{4}=\frac{\pi}{\omega}\left(\rm{erf}\left[\sigma\left(\frac{\omega}{2}-\Omega\right)\right]+\rm{erf}\left[\sigma\left(\frac{\omega}{2}+\Omega\right)\right]-e^{-\frac{D^{2}}{4\sigma^{2}}}\rm{Re}\left[Q_{+}R_{+}+Q_{-}R_{-}\right]\right),$

with
$Q_{\pm}:=-ie^{iD\left(\frac{\omega}{2}\pm\Omega\right)}\rm{erf}{\left[i\frac{D}{2\sigma}+\sigma\left(\frac{\omega}{2}\pm\Omega\right)\right]}$
and
$R_{\pm}:=\frac{D}{2}\left(\frac{\omega}{2}\pm\Omega\right)+i\left(1+\frac{D^{2}}{4\sigma^{2}}\right)$.

##  IV Quantum steering and Bell nonlocality of two Unruh-DeWitt detectors

In this section, we will consider how gravitational waves affect vacuum
steering and Bell nonlocality, exploring gravitational wave-assisted steering
harvesting and the harvesting-achievable range of gravitational waves
extending quantum steering. Employing Eqs.(20) and (33), we can obtain an
analytic expression of the steering $T^{A\rightarrow B}$ as

$T^{A\rightarrow
B}=\max\\{0,\frac{8}{\sqrt{3}}(|X|^{2}-\frac{\sqrt{3}}{2}P^{2}-\frac{1}{2}P),\frac{8}{\sqrt{3}}(|C|^{2}+\frac{\sqrt{3}}{2}P^{2}-\frac{1}{2}P)\\}.$
(40)

Here, the expressions for both quantum steering, $T^{B\rightarrow A}$ and
$T^{A\rightarrow B}$, are identical. Therefore, our analysis will focus solely
on the steering $T^{A\rightarrow B}$. To observe the direct impact of
gravitational waves on vacuum steering, we also investigate the steering
$S^{A\rightarrow B}$ in Minkowski spacetime.

Figure 1: Quantum steering of two detectors in the background of gravitational
waves and in Minkowski spacetime as a function of the gravitational wave
frequency $\omega\sigma$ for various values of the energy gap $\Omega\sigma$
and $t_{0}/\sigma$ with $D/\sigma=0.5$.

In Fig.1, we plot quantum steering $T^{A\rightarrow B}$ (in the background of
gravitational waves) and $S^{A\rightarrow B}$ (in Minkowski spacetime) as a
function of the gravitational wave frequency $\omega\sigma$ for different
energy gaps $\Omega\sigma$ and $t_{0}/\sigma$. We find that quantum steering
$T^{A\rightarrow B}$ cannot be harvested from the vacuum at the lower
gravitational wave frequency $\omega\sigma$, while quantum steering
$S^{A\rightarrow B}$ can be harvested in Minkowski space. We also find that
when the gravitational wave frequency $\omega\sigma$ is much greater than the
energy gap $\Omega\sigma$, quantum steerability $T^{A\rightarrow B}$ is
approximately equal to quantum steerability $S^{A\rightarrow B}$, which means
that the gravitational wave does not influence the harvested steering
significantly. From Fig.1, we can see that when the frequency of gravitational
waves is roughly equal to the energy gap of the detector, that is, when
$\omega\approx 2\Omega$, a strong resonance effect will occur, leading to
maximized harvest of quantum steering around this frequency. For
$\Omega\sigma=2$, it is shown that quantum steerability $S^{A\rightarrow B}$
equals zero, while gravitational waves can create quantum steering harvested
from the vacuum, reflecting that gravitational waves can broaden the parameter
range for harvested steering. From Fig.1, we also see that quantum
steerability $T^{A\rightarrow B}$ can be greater than or less than quantum
steerability $S^{A\rightarrow B}$, indicating that the gravitational wave can
either amplify or degrade the harvested steerability. For a smaller energy gap
$\Omega\sigma$, quantum steerability $T^{A\rightarrow B}$ for $t_{0}/\sigma=1$
is generally larger than quantum steerability $T^{A\rightarrow B}$ for
$t_{0}/\sigma=0$ in most parameter spaces. Conversely, for a larger energy gap
$\Omega\sigma$, this situation is completely opposite to the above situation.
Additionally, for a larger gravitational wave frequency $\omega\sigma$, Fig.1
shows that quantum steering $T^{A\rightarrow B}$ is independent of
$t_{0}/\sigma$.

Figure 2: Quantum steering between two detectors in the background of
gravitational waves and in Minkowski spacetime as a function of the detector
separation $D/\sigma$.

In Fig.2, we illustrate the variation of quantum steering with respect to the
detector separation $D/\sigma$. We find that harvested steering
$T^{A\rightarrow B}$ and $S^{A\rightarrow B}$ first monotonically decrease and
then suffer “sudden death” with the increase of the detector separation
$D/\sigma$, meaning that reducing detector separation is beneficial for vacuum
steering. From left column of Fig.2, we can see that the harvesting-achievable
separation range of $T^{A\rightarrow B}$ is smaller than the harvesting-
achievable separation range of $S^{A\rightarrow B}$, indicating that the
presence of gravitational waves can shorten the harvesting-achievable
separation range. From right column of Fig.2, we also see that the harvesting-
achievable separation range of $T^{A\rightarrow B}$ is wider than the
harvesting-achievable separation range of $S^{A\rightarrow B}$, showing that
the presence of gravitational waves can widen the harvesting-achievable
separation range. From Fig.2, we can conclude that the presence of
gravitational waves can broaden or narrow harvesting-achievable separation
range of vacuum steering, depending on $t_{0}/\sigma$, $\Omega\sigma$, and
$\omega\sigma$.

Figure 3: Bell signal of two detectors under the influence of gravitational
waves and in Minkowski spacetime is plotted as a function of the gravitational
wave frequency $\omega\sigma$ for various values of the energy gap
$\Omega\sigma$ and $t_{0}/\sigma$ with $D/\sigma=0.5$.

Similar to the research on vacuum steering, we also study Bell nonlocality for
the bipartite system in the context of gravitational waves. Using Eqs.(25) and
(33), the expression of Bell signal $B$ under the influence of gravitational
waves can be found to be

$B(\rho_{AB})=\max\\{4\sqrt{2(|X|^{2}+|C|^{2})},{2\sqrt{4(|X|+|C|)^{2}+(|1-2P|-2|P|)^{2}}\\}}.$
(41)

In order to facilitate the detection of the effects of gravitational waves on
Bell nonlocality, we also explore Bell signal in Minkowski spacetime, labeled
$\bar{B}$.

A more detailed study of the influence of gravitational waves on Bell signal
is shown in Fig.3, where $B$ and $\bar{B}$ are plotted as a function of the
gravitational wave frequency $\omega\sigma$ for different $\Omega\sigma$ and
$t_{0}/\sigma$. From Fig.3, we can see that Bell signal is always less than 2
regardless of the presence of the gravitational wave. In other words, the
system of two detectors that does not violate the Bell inequality is
considered to have no quantum nonlocality. Therefore, we can conclude that the
existence of gravitational waves does not produce Bell nonlocality harvested
from the vacuum. Consequently, harvested steering cannot be regarded as
nonlocal.

##  V Conclusion

The effect of gravitational waves on vacuum steering and Bell nonlocality
harvested by two UDW detectors has been investigated. We obtain a description
of how steering in the background of gravitational waves and in Minkowski
spacetime vary with the gravitational wave frequency. It is shown that for
smaller energy gaps, quantum steering cannot be harvested from the vacuum at
the lower gravitational wave frequency, whereas it can be harvested in
Minkowski spacetime. However, for larger energy gaps, quantum steering cannot
be harvested from the vacuum in Minkowski spacetime, while the gravitational
waves can create net quantum steering. This implies that gravitational waves
can either amplify or diminish the harvested steerability, with the outcome
depending on the energy gap. Quantum steering under the influence of
gravitational waves is nearly equal to quantum steering in Minkowski spacetime
when the gravitational wave frequency is much larger than the energy gap. The
above phenomenon implies that the gravitational waves have no significant
effect on steering harvesting. It is intriguing to find that a strong
resonance effect for harvested steering occurs when the energy gap of the
detectors is tuned to the frequency of the gravitational wave.

To explore the effect of gravitational waves on the harvesting-achievable
range of vacuum steering, we obtain a description of how steering changes with
detector separation in the background of gravitational waves and in Minkowski
spacetime. We find that the harvested steering first decreases monotonically
and then experiences “sudden death” as the detector separation increases. We
also find that the presence of gravitational waves can widen or narrow
harvesting-achievable separation range of vacuum steering relative to
Minkowski spacetime, which is related to the energy gap, the gravitational
wave frequency, and the duration of the gravitational wave action.
Furthermore, Bell signal is not more than 2, which satisfies the Bell
inequality. The result shows that the presence of gravitational waves cannot
generate Bell nonlocality harvested from the vacuum. Therefore, harvesting
steering cannot be regarded as nonlocal.

###### Acknowledgements.

This work is supported by the National Natural Science Foundation of China
(Grant Nos. 12205133), LJKQZ20222315, and Scientific and Technological
Innovation Programs of Higher Education Institutions of Shanxi Province, China
(2023L327).

## References

  * (1) E. Schrödinger, Discussion of probability relations between separated systems, Proc. Cambridge Philos. Soc. 31, 555 (1935).
  * (2) E. Schrödinger, Probability relations between separated systems, Proc. Cambridge Philos. Soc. 32, 446 (1936).
  * (3) J. Wang, H. Cao, J. Jing, and H. Fan, Gaussian quantum steering and its asymmetry in curved spacetime, Phys. Rev. D 93, 125011 (2016).
  * (4) A. Einstein, B. Podolsky, and N. Rosen, Can quantum-mechanical description of physical reality be considered complete?, Phys. Rev. 47, 777 (1935).
  * (5) M. D. Reid, P. D. Drummond, W. P. Bowen, E. G. Cavalcanti, P. K. Lam, H. A. Bachor, U. L. Andersen, and G. Leuchs, Colloquium: The Einstein-Podolsky-Rosen paradox: From concepts to applications, Rev. Mod. Phys. 81, 1727 (2009).
  * (6) J. S. Bell, On the Einstein-Podolsky-Rosen paradox, Physics 1, 195 (1964).
  * (7) S. M. Wu, H. S. Zeng, Genuine tripartite nonlocality and entanglement in curved spacetime, Eur. Phys. J. C 82, 4 (2022).
  * (8) C. Wen, J. Wanga, J. Jing, Quantum steering for continuous variable in de Sitter space, Eur. Phys. J. C 80, 78 (2020).
  * (9) R. Uola, A.C.S. Costa, H.C. Nguyen, O. Guhne, Quantum steering, Rev. Mod. Phys. 92, 015001 (2020).
  * (10) B. Hu, C. Wena, J. Wang, J. Jing, Gaussian quantum steering under the influence of a dilaton black hole, Eur. Phys. J. C 81, 925 (2021).
  * (11) P. Skrzypczyk, M. Navascués, D. Cavalcanti, Quantifying Einstein-Podolsky-Rosen Steering, Phys. Rev. Lett. 112, 180404 (2014).
  * (12) S. P. Walborn, A. Salles, R. M. Gomes, F. Toscano, P. H. Souto Ribeiro, Revealing hidden Einstein-Podolsky-Rosen nonlocality, Phys. Rev. Lett. 106, 130402 (2011).
  * (13) J. Bowles, T. Vértesi, M. T. Quintino, N. Brunner, One-way Einstein-Podolsky-Rosen steering, Phys. Rev. Lett. 112, 200402 (2014).
  * (14) A. B. Sainz, N. Brunner, D. Cavalcanti, P. Skrzypczyk, T. Vértesi, Postquantum steering, Phys. Rev. Lett. 115, 190403 (2015).
  * (15) V. Händchen, T. Eberle, S. Steinlechner, A. Samblowski, T. Franz, R. F. Werner, R. Schnabel, Observation of one-way Einstein-Podolsky-Rosen steering, Nat. Photon. 6, 598 (2012).
  * (16) S. Wollmann, R. Uola, A. C. S. Costa, Experimental demonstration of robust quantum steering, Phys. Rev. Lett. 125, 020404 (2020).
  * (17) M. Piani and J. Watrous. Necessary and sufficient quantum information characterization of Einstein-Podolsky-Rosen steering. Phys. Rev. Lett. 114 060404 (2015).
  * (18) P. Skrzypczyk and D. Cavalcanti, Maximal randomness generation from steering inequality violations using qudits, Phys. Rev. Lett. 120, 260401 (2018).
  * (19) Q. Y. He, Q. H. Gong, M. D. Reid, Classifying directional Gaussian entanglement, Einstein-Podolsky-Rosen steering, and discord, Phys. Rev. Lett. 114, 060402 (2015).
  * (20) M. D. Reid. Signifying quantum benchmarks for qubit teleportation and secure quantum communication using Einstein-Podolsky-Rosen steering inequalities. Phys. Rev. A, 88 062338, (2013).
  * (21) H. Buhrman, R. Cleve, S. Massar, R. D. Wolf, Nonlocality and communication complexity, Rev. Mod. Phys. 82, 665 (2010).
  * (22) C. H. Bennett, G. Brassard, N. D. Mermin, Quantum cryptography without Bell’s theorem, Phys. Rev. Lett. 68, 557 (1992).
  * (23) C. Dhara, G. Prettico, A. Antonio, Maximal quantum randomness in Bell tests, Phys. Rev. A 88, 052116 (2013).
  * (24) J. Barrett, L. Hardy, A. Kent, No signaling and quantum key distribution, Phys. Rev. Lett. 95, 010503 (2005).
  * (25) C. H. Bennett et al., Quantum nonlocality without entanglement, Phys. Rev. A 59, 1070 (1999).
  * (26) S. Popescu, D. Rohrlich, Nonlocality as an axiom, Found. Phys. 24, 379 (1994).
  * (27) W. Cong, C. Qian, M. R. R. Good, R. B. Mann, Effects of Horizons on Entanglement Harvesting, J. High Energ. Phys. 10, 067 (2020).
  * (28) W. Cong, E. Tjoa, R. B. Mann, Entanglement harvesting with moving mirrors, J. High Energ. Phys. 06, 021 (2019).
  * (29) A. Valentini, Non-local correlations in quantum electrodynamics, Phys. Lett. A 153, 321 (1991).
  * (30) W. G. Unruh, Notes on black-hole evaporation, Phys. Rev. D 14, 870 (1976).
  * (31) B. DeWitt, General Relativity; an Einstein Centenary Survey (Cambridge University Press, Cambridge, UK, 1980).
  * (32) B. Reznik, A. Retzker, and J. Silman, Violating Bell’s inequalities in vacuum, Phys. Rev. A 71, 042104 (2005).
  * (33) Z. Liu, J. Zhang, R. B. Mann, and H. Yu, Does acceleration assist entanglement harvesting?, Phys. Rev. D 105, 085012 (2022).
  * (34) Z. Liu, J. Zhang, H. Yu, Harvesting correlations from vacuum quantum fields in the presence of a reflecting boundary, J. High Energ. Phys. 11, 184 (2023).
  * (35) A. Pozas-Kerstjens and E. Martín-Martínez, Harvesting correlations from the quantum vacuum, Phys. Rev. D 92, 064042 (2015).
  * (36) D. Barman and B. R. Majhi, Are multiple reflecting boundaries capable of enhancing entanglement harvesting?, Phys. Rev. D 108, 085007 (2023).
  * (37) S. Barman, I. Chakraborty, S. Mukherjee, Entanglement harvesting for different gravitational wave burst profiles with and without memory, J. High Energ. Phys. 09, 180 (2023).
  * (38) T. R. Perche, B. Ragula, and E. Martín-Martínez, Harvesting entanglement from the gravitational vacuum, Phys. Rev. D 108, 085025 (2023).
  * (39) H. Maeso-García, J. Polo-Gómez, and E. Martín-Martínez, How measuring a quantum field affects entanglement harvesting, Phys. Rev. D 107, 045011 (2023).
  * (40) Z. Liu, J. Zhang, and H. Yu, Entanglement harvesting of accelerated detectors versus static ones in a thermal bath, Phys. Rev. D 107, 045010 (2023).
  * (41) H. Maeso-García, J. Polo-Gómez, and E. Martín-Martínez, Entanglement harvesting: State dependence and covariance, Phys. Rev. D 106, 105001 (2022).
  * (42) H. Maeso-García, J. Polo-Gómez, and E. Martín-Martínez, Entanglement harvesting: Detector gap and field mass optimization, Phys. Rev. D 106, 045014 (2022).
  * (43) D. Barman, S. Barman, and B. R. Majhi, Entanglement harvesting between two inertial Unruh-DeWitt detectors from nonvacuum quantum fluctuations, Phys. Rev. D 106, 045005 (2022).
  * (44) H. Hu, J. Zhang, H. Yu, Harvesting entanglement by non-identical detectors with different energy gaps, J. High Energ. Phys. 05, 112 (2022).
  * (45) S. Barman, D. Barman, B. R. Majhi, Entanglement harvesting from conformal vacuums between two Unruh-DeWitt detectors moving along null paths, J. High Energ. Phys. 09, 106 (2022).
  * (46) T. R. Perche, C. Lima, and E. Martín-Martínez, Harvesting entanglement from complex scalar and fermionic fields with linearly coupled particle detectors, Phys. Rev. D 105, 065016 (2022).
  * (47) P. Chowdhury, B. R. Majhi, Fate of entanglement between two Unruh-DeWitt detectors due to their motion and background temperature, J. High Energ. Phys. 05, 025 (2022).
  * (48) D. Barman, S. Barman, B. R. Majhi, Role of thermal field in entanglement harvesting between two accelerated Unruh-DeWitt detectors, J. High Energ. Phys. 07, 124 (2021).
  * (49) E. Tjoa, R. B. Mann, Harvesting correlations in Schwarzschild and collapsing shell spacetimes, J. High Energ. Phys. 08, 155 (2020).
  * (50) S. M. Wu, H. S. Zeng, Fermionic steering and its monogamy relations in Schwarzschild spacetime, Eur. Phys. J. C 82,716 (2022).
  * (51) S. M. Hashemi Rafsanjani, M. Huber, C. J. Broadbent, J. H. Eberly, Genuinely multipartite concurrence of N-qubit X matrices, Phys. Rev. A 86, 062303 (2012).
  * (52) D. Das, S. Sasmal, S. Roy, Detecting Einstein-Podolsky-Rosen steering through entanglement detection, Phys. Rev. A 99, 052109 (2019).
  * (53) K. Zhang, J. Wang, Asymmetric steerability of quantum equilibrium and nonequilibrium steady states through entanglement detection, Phys. Rev. A 104, 042404 (2021).
  * (54) J. F. Clauser, M. A. Horne, A. Shimony, R. A. Holt, Proposed experiment to test local hidden-variable theories, Phys. Rev. Lett. 23, 880 (1969).
  * (55) R. Horodecki, P. Horodecki, M. Horodecki, Violating Bell inequality by mixed spin-$\frac{1}{2}$ states: necessary and sufficient condition, Phys. Lett. A 200, 340 (1995).
  * (56) P. Shadbolt et al., Guaranteed violation of a bell inequality without aligned reference frames or calibrated devices, Sci. Rep. 2, 470 (2012).
  * (57) W. Y. Sun, D. Wang, J. D. Shi, L. Ye, Exploration quantum steering, nonlocality and entanglement of two-qubit X-state in structured reservoirs, Sci. Rep. 7, 39651 (2017).
  * (58) J. Garriga and E. Verdaguer, Scattering of quantum particles by gravitational plane waves, Phys. Rev. D 43, 391 (1991).
  * (59) Q. Xu, S. A. Ahmad, and A. R. H. Smith, Gravitational waves affect vacuum entanglement, Phys. Rev. D 102, 065019 (2020).


11institutetext: Department of Informatics, University of Bergen, Norway
11email<EMAIL_ADDRESS>22institutetext: School of Computer
Sciences, NISER, Bhubaneswar, India
22email<EMAIL_ADDRESS>33institutetext: Algorithms and Complexity
Group, Technische Universität Wien, Austria
33email<EMAIL_ADDRESS>
# Geometric Planar Networks
on Bichromatic Points††thanks:  Research of Sujoy Bhore and Martin Nöllenburg
is supported by the Austrian Science Fund (FWF) grant P 31119.

Sayan Bandyapadhyay 11 Aritra Banik 22 Sujoy Bhore 33 Martin Nöllenburg 33

###### Abstract

We study four classical graph problems – Hamiltonian path, Traveling salesman,
Minimum spanning tree, and -Minimum perfect matching on geometric graphs
induced by bichromatic (red and blue) points. These problems have been widely
studied for points in the Euclidean plane, and many of them are
$\mathsf{NP}$-hard. In this work, we consider these problems in two restricted
settings: (i) collinear points and (ii) equidistant points on a circle. We
show that almost all of these problems can be solved in linear time in these
constrained, yet non-trivial settings.

##  1 Introduction

In this article, we study four classical graph problems on geometric graphs
induced by bichromatic (red and blue) points. Suppose, we are given a set $R$
of $n$ red points and a set $B$ of $m$ blue points in the Euclidean plane.
Consider the complete bipartite graph $G(R,B,E)$ on $R\cup B$, where the set
$E$ of edges contains all bichromatic edges between the red points and the
blue points. Also, suppose the graph $G(R,B,E)$ is embedded in the plane: the
points are the vertices and each edge is represented by the segment between
the two corresponding endpoints. We denote these edges as _bichromatic
segments_ , where each bichromatic segment connects a red point with a blue
point. A subgraph of $G(R,B,E)$ (or equivalently a subset of edges of $E$) is
called non-crossing (or planar) if no pair of the edges of the subgraph cross
each other. Next, we discuss the four graph problems on the bipartite graph
$G(R,B,E)$ induced by $R\cup B$.

In the Bichromatic Hamiltonian path problem, the objective is to find a path
in $G(R,B,E)$ that spans all the red and blue points. Equivalently, one would
like to find a polygonal chain that connects all the red points and the blue
points alternately through bichromatic segments. It is not hard to see that a
Hamiltonian path exists in $G(R,B,E)$ if and only if $m-1\leq n\leq m+1$, and
if there exists one, it can be computed efficiently, as $G(R,B,E)$ is a
complete bipartite graph. A more interesting problem is the Non-crossing
bichromatic Hamiltonian path problem where the objective is to find a non-
crossing Hamiltonian path. Note that one can construct instances with $m-1\leq
n\leq m+1$, where it is not possible to find any non-crossing Hamiltonian
path. In Figure 1, we demonstrate two such instances.111In all the figures
throughout the paper, we show red (resp. blue) points by squares (resp.
disks). Figure 1(a) has eight points where four of them lie on a horizontal
line $L$ and the remaining four lie on a line parallel to $L$. Notice that,
there must be one red and one blue point with degree $1$. One can verify by
enumerating all possible paths that there is no non-crossing Hamiltonian path
that spans these points. The example in Figure 1(b) has thirteen points in
general position, i.e., no pair of the points are collinear, and also does not
admit a non-crossing Hamiltonian path. Indeed, if $2\leq n\leq 12$, then for
any given $\lfloor{n/2}\rfloor$ red (resp. blue) points and
$\lceil{n/2}\rceil$ blue (resp. red) points in general position, there exists
a non-crossing Hamiltonian path [13]. Due to the uncertainty of the existence
of non-crossing Hamiltonian paths in the general case, researchers have also
considered the problem of finding a non-crossing alternating path of length as
large as possible [11, 15].

Figure 1: Two instances without a non-crossing Hamiltonian path. Figure (a) is
not in general position, Figure (b) (borrowed from [12]) is in general
position.

A related problem is the Bichromatic traveling salesman path (Bichromatic TSP)
problem where one would like to find a minimum weight Hamiltonian path in
$G(R,B,E)$. The weight of each edge is the (Euclidean) length of the
corresponding segment. The weight of a path is the sum of the weights of the
edges along the path. For simplicity, we assume $n=m$. A straightforward
reduction from the (monochromatic) Euclidean TSP [4] (replace each point by a
bichromatic pair that is small distance apart) shows that Bichromatic TSP is
also $\mathsf{NP}$-hard. One simple, but powerful fact is that an optimum
Euclidean TSP is always non-crossing. This helps to obtain a PTAS [4] for the
problem. However, an optimum Bichromatic TSP is not necessarily non-crossing
which makes its computation much harder compared to Euclidean TSP. The best
known approximation factor for the Bichromatic TSP problem is $2$ due to Frank
et al. [10] who improved the $2.5$-approximation of Anily et al. [3]. For a
set of collinear points, Evans et al. [9] gave a quadratic time algorithm for
computing an optimum non-crossing TSP, every edge of which is a poly-line with
at most two bends.

Next, we consider the Bichromatic spanning tree problem where the objective is
to compute a minimum weight spanning tree of $G(R,B,E)$. Note that this
problem can be solved efficiently by any standard minimum spanning tree
algorithm. A more interesting problem is the Non-crossing bichromatic spanning
tree problem where additionally the computed tree must be planar (non-
crossing). Borgelt et al. [8] showed that this problem is $\mathsf{NP}$-hard.
For points in general position, they gave a near-linear time
$O(\sqrt{n})$-approximation. On the other hand, for points in convex position,
they gave an exact cubic-time algorithm. Another line of work that received
much attention is where the task is to find a degree-bounded non-crossing
spanning tree [7].

Finally, we consider the Bichromatic matching problem. Again assume that $n=m$
for simplicity. We would like to find a minimum weight perfect matching in
$G(R,B,E)$. The weight of an edge is the Euclidean distance between its
corresponding points. It is a well-known fact that a minimum weight
bichromatic matching (for points in general position) in the plane is always
non-crossing, which follows from the observation that the sum of the diagonals
of a convex quadrilateral is strictly larger than the sum of any pair of
opposite sides. This implies that using any standard bipartite matching
algorithm one can solve Bichromatic matching exactly. But, algorithms with
better running time have been designed by exploiting the underlying geometry
of the plane. Recently, Kaplan et al. [14] designed an
$O(n^{2}\operatorname{poly}(\log n))$ algorithm for the problem improving the
$O(n^{2+\epsilon})$ algorithm due to Agarwal et al. [2], where
$\operatorname{poly}(.)$ is a polynomial function. Abu-Affash _et al._ [1] and
Biniaz _et al._ [6] studied variants of the bichromatic matching problem.

In this article, we consider the above mentioned problems in two restricted
settings: (i) for collinear points and (ii) for equidistant points on a
circle. For all problems, we assume that $n=m$ for simplicity. We note that
the case of non-crossing graphs on collinear points is closely related to
topological 1-page or 2-page book embeddings [5], which have all vertices
placed on a line (called the spine) and the edges drawn without crossings in
one or two of the halfplanes (but not in both) defined by the spine (called
the pages). In our case we assume that the edges are drawn as (circular) arcs
or 1-bend polylines either above or below the spine.222For the sake of
convenience, we draw edges as simple curves in all the figures. We assume that
their weight is given by the Euclidean distance of their endpoints. If the
arcs are drawn infinitesimally close to the spine, these weights correspond to
the lengths of the arcs.

Our Results. The main results obtained in this work are the following.

  1. ➥

Non-crossing Hamiltonian path for collinear points – We prove that for any
collinear configuration of the points, there always exists a non-crossing
Hamiltonian path. We give a linear-time algorithm for computing such a path
(Section 2).

  2. ➥

Minimum spanning tree for collinear points – We give a linear-time algorithm
for computing a minimum weight spanning tree, and a quadratic-time algorithm
for computing a minimum weight non-crossing spanning tree for collinear points
and edges on a single page (Section 3).

  3. ➥

Minimum non-crossing matching for collinear points – We give a linear-time
algorithm that computes a minimum-weight non-crossing perfect matching for
collinear points and edges on a single page (Section 4).

  4. ➥

TS tour for chunked points on a circle – We give a linear-time algorithm for
computing an optimum traveling salesman tour for equidistant points on a
circle that form alternately colored and equally sized chunks (Section 5).

The linear-time algorithms assume that the points are given in some sorted
order. We note that even in this simple one-dimensional case these problems
become sufficiently challenging if one is constrained to use only linear (or
near-linear) time. Throughout the paper we assume that there are no collocated
points.

##  2 Non-crossing Hamiltonian Path for Collinear Points

If we would require for the collinear point set that each edge of a
Hamiltonian path is a straight-line segment the problem becomes trivial: an
input instance can have a non-crossing Hamiltonian path if and only if the
colors of the points alternate. Therefore, we consider the case where edges
are represented by circular arcs drawn in the halfplane either above or below
the line.

###### Definition 1

Non-crossing Hamiltonian path for collinear points. Given a set of $n$ red
points and a set of $n$ blue points on the line $H\colon y=0$, find a non-
crossing geometric path $\pi$ in the plane such that $\pi$ consists of
circular arcs above or below $H$, each of which connects a red and a blue
point and $\pi$ spans all the input points.

Note that in the above definition if the path is allowed to use arcs only from
above (resp. below) $H$, then there might not exist such a Hamiltonian path
(see Figure 2).

Figure 2: Figure demonstrating a set of collinear points for which non-
crossing Hamiltonian path does not exist if the arcs can be drawn only above
the line.

First, we give a constructive proof for the existence of such a path for any
configuration of points. The construction itself takes polynomial time, hence
giving a polynomial time algorithm for computation of such a path. In the
following, we describe the construction.

###  2.1 The Construction

To construct the path, we start with any bichromatic matching (not necessarily
crossing free) of the points. Note that each matched edge is a segment on $H$.
We will connect these edges to obtain a Hamiltonian path. First, we form a
hierarchical structure of these matched edges. Informally, the matched edges
are hierarchical if any two edges are either disjoint or one is contained
within the other.

###### Definition 2

A set of matched edges $M$ are hierarchical if for any two edges
$(u,v),(w,x)\in M$ with $u<v$, $w<x$ and $u<w$, either $u<v<w<x$
($(u,v),(w,x)$ are uncrossed) or $u<w<x<v$ $((u,v)$ contains $(w,x))$.

Given any matching $M$ for $R\cup B$, we can change it to a hierarchical
matching in the following way. If there are two edges $(u,v),(w,x)\in M$ with
$u<v$, $w<x$, $u<w$ that are not disjoint and none of them contains the other,
then it must be the case that $u<w<v<x$. Now, there are two subcases,
depending on the colors of $u$ and $w$. If $u,w$ are red or $u,w$ are blue, we
replace the edges $(u,v),(w,x)$ by the two bichromatic edges $(u,x),(w,v)$.
Otherwise, either $u$ is red, $w$ is blue or $u$ is blue, $w$ is red. In that
case, we replace the edges $(u,v),(w,x)$ by the two bichromatic edges
$(u,w),(v,x)$. Note that in all the cases, the new pair of edges do not
violate the hierarchical structure. We repeat the process for each pair of
edges that violate the condition. Newly formed edges might violate the
condition with respect to other edges. However, it is easy to verify that if
an edge is removed, it is never added back, and thus the process will
eventually stop at some point when no pair of edges violate the condition.

Next, we associate levels with each matched edge of $M$ in a recursive way. In
the base case, for each edge that does not span any other edge, set its level
to 1. Now, suppose we have defined edges of level $j$ for each $j\leq i-1$ for
$i\geq 2$. An edge $(u,v)$ has level $i$, if it contains a level $i-1$ edge,
and for any level $i-1$ edge $(w,x)$ that it contains, there is no other edge
that is contained in $(u,v)$ that also contains $(w,x)$ (see Figure 3). Note
that the level of each edge is unique. Let $L$ be the maximum level.

Figure 3: Illustration showing the levels of the edges.

For any edge $(u,v)$ of $M$ with level $j$, call the points that lie between
$u$ and $v$ including $u$ and $v$ as a level $j$ block. Thus, a level $l$
block is a union of blocks of levels at most $l-1$ and two special points
which are the first and last point of the block. One can easily verify that a
block contains the same number of red and blue points. We compute the
Hamiltonian path for all the blocks in a bottom up manner. The path of a level
1 block is the matched edge itself which defines the block. Additionally, for
each block, we compute a path for the block that satisfies the following two
invariants.

  * •

The first point of the block is an endpoint of the path.

  * •

If an endpoint $p$ of the path is not an endpoint of the block, then the path
cannot contain two edges $(u,v),(w,x)$ with $u<v$ and $w<x$, such that $(u,v)$
lies above $H$, $(w,x)$ lies below $H$, $u<p<v$, and $w<p<x$.

Informally, the second condition states that, the endpoint of the path that is
not an endpoint of the block should be available for connecting with an edge
at least from one side. Note that the paths for level 1 blocks trivially
satisfy the invariants. Now, assume that we have computed the paths for all
the level $j$ blocks for $j\leq l-1$ and $l\geq 2$ that satisfy the
invariants. We show how to compute the path for a level $l$ block $S$ that
also satisfies the invariants. Let $u,v$ be the endpoints of the block. Also
let $S_{1},\ldots,S_{t}$ be the blocks, sorted w.r.t the index of the first
point in increasing order, whose union with the set $\\{u,v\\}$ forms the
block $S$. As $S_{i}$ has level at most $l-1$, we have already computed the
path of $S_{i}$ for all $i$. We show, by induction, how to construct the path
$T^{\prime}$ for the points in $\cup_{j=1}^{i}S_{j}$ for all $2\leq i\leq t$.
Then, we show how to join the edge $(u,v)$ with $T^{\prime}$ to obtain the
path for the block $S$. For simplicity, we also refer to the set of points
$\cup_{j=1}^{i}S_{j}$ as a block. Now, we prove the following lemma.

###### Lemma 1

A non-crossing Hamiltonian path of $\cup_{j=1}^{i}S_{j}$ can be computed for
all $1\leq i\leq t$ that satisfies the two invariants.

Figure 4: Illustration showing Case 1 (upper) and Case 2 (lower) of Lemma 1.

###### Proof

We prove this using induction on the values of $i$. In the base case, for
$i=1$, we know how to compute the path of $\cup_{j=1}^{i}S_{j}=S_{1}$ that
satisfies the two invariants. Now, consider any $i\geq 2$. Suppose we have
already computed the path $T_{i-1}$ of $\cup_{j=1}^{i-1}S_{j}$ that satisfies
the two invariants. Let $\Pi_{i}$ be the path of $S_{i}$ that also satisfies
the two invariants. Let $u_{1},v_{1}$ (resp. $u_{2},v_{2}$) be the endpoints
of the path $T_{i-1}$ (resp. $\Pi_{i}$) with $u_{1}<v_{1}$ (resp.
$u_{2}<v_{2}$). As $\cup_{j=1}^{i-1}S_{j}$ (resp. $S_{i}$) contains the same
number of red and blue points, the color of $u_{1}$ (resp. $u_{2}$) will be
different from the color of $v_{1}$ (resp. $v_{2}$). Now, there are two cases.

#### _$1.$ $u_{1}$ and $u_{2}$ have the same color._

We add the edge $(v_{1},u_{2})$ with $T_{i-1}\cup\Pi_{i}$ to get the path
$T_{i}$ for $\cup_{j=1}^{i}S_{j}$ (see Figure 4). To make sure $(v_{1},u_{2})$
does not cross the other edges, we can make use of the second invariant. From
the invariant it follows that, for $v_{1}$, all the edges of $T_{i-1}$ whose
endpoints are on both sides of $v_{1}$ must lie on the same side of $H$. Thus,
if those edges lie above, we draw the edge $(v_{1},u_{2})$ below $H$.
Otherwise, we draw $(v_{1},u_{2})$ above $H$. Note that $u_{1}$ is an endpoint
of $T_{i}$ which is the first point of $\cup_{j=1}^{i}S_{j}$. Also
$v_{1}<u_{2}<v_{2}$. Thus, the other endpoint $v_{2}$, still satisfies the
second invariant as before by induction.

#### _$2.$ $u_{1}$ and $u_{2}$ have different colors._

We add the edge $(v_{1},v_{2})$ with $T_{i-1}\cup\Pi_{i}$ to get the path
$T_{i}$ for $\cup_{j=1}^{i}S_{j}$ (see Figure 4). Note that we need to ensure
that the edges of $T_{i-1}$ and $\Pi_{i}$ whose endpoints are on both sides of
$v_{1}$ and $v_{2}$, respectively, lie on the same side of $H$. Note that if
this is not true, the edges of $\Pi_{i}$ that lie below $H$ can be redrawn
above $H$, and the edges of $\Pi_{i}$ that lie above $H$ can be redrawn below
$H$. This does not violate any invariant. Hence, $(v_{1},v_{2})$ can be drawn
without crossing any edge of $T_{i-1}\cup\Pi_{i}$. Note that $u_{1}$ is an
endpoint of $T_{i}$ which is the first point of $\cup_{j=1}^{i}S_{j}$. The
other endpoint $u_{2}$ was an endpoint of the block $S_{i}$. Thus, even after
the drawing of $(v_{1},v_{2})$ one side of $u_{2}$ still remains available.
Hence, the second invariant is also satisfied. ∎

The next lemma completes the induction step for showing the construction of
the path for the level $l$ block.

###### Lemma 2

A non-crossing Hamiltonian path for the level $l$ block $S$ can be computed
that satisfies the two invariants.

Figure 5: (a) Illustration showing Case 1 of Lemma 2. (b) Illustration showing
Case 2 of Lemma 2.

###### Proof

First, we compute the path $T_{t}$ for the points in $\cup_{j=1}^{t}S_{j}$
using the construction in Lemma 1. Let $u_{1},v_{1}$ be the endpoints of
$T_{t}$ such that $u_{1}<v_{1}$. Note that as mentioned before
$S=(\cup_{j=1}^{t}S_{j})\cup\\{u,v\\}$. WLOG, assume the color of $u$ and $v$
is red and blue, respectively. The other case can be handled similarly. Now,
there can be two cases.

#### _$1.$ $u_{1}$ is red and $v_{1}$ is blue._

We add the edge $(u_{1},v)$ with $T_{t}\cup\\{(u,v)\\}$ to get the path for
$S$ (see Figure 5(a)). From the second invariant for $T_{t}$ it follows that,
for $v_{1}$, all the edges of $T_{t}$ whose endpoints are on both sides of
$v_{1}$ must lie on the same side of $H$. Thus, if those edges lie above, we
draw the edges $(u_{1},v),(u,v)$ above $H$. Otherwise, we draw
$(u_{1},v),(u,v)$ below $H$. Thus, the second invariant is satisfied. Also,
note that $u$ is an endpoint of the new path which is the first point of $S$.
Hence, both the invariants are satisfied.

#### _$2.$ $u_{1}$ is blue and $v_{1}$ is red._

We add the edge $(v_{1},v)$ with $T_{t}\cup\\{(u,v)\\}$ to get the path for
$S$ (see Figure 5(b)). From the second invariant for $T_{t}$ it follows that,
for $v_{1}$, all the edges of $T_{t}$ whose endpoints are on both sides of
$v_{1}$ must lie on the same side of $H$. Thus, if those edges lie above, we
draw the edge $(v_{1},v)$ below $H$. Otherwise, we draw $(v_{1},v)$ above $H$.
As $u_{1}$, an endpoint of the new path, is the second point of $S$,
irrespective of how we draw $(u,v)$, the second invariant is satisfied. Also
$u$ is an endpoint of the new path which is the first point of $S$. Hence,
both the invariants are satisfied in this case as well. ∎

To compute the path of all the points in $R\cup B$ one can note that $R\cup B$
is a union of a set of blocks having levels at most the maximum level $L$. By
Lemma 2, we can compute the paths for all such blocks that satisfy the
invariants. Then we can merge those paths using the construction in Lemma 1 to
get the path for the points in $R\cup B$. It is easy to verify that the
overall construction can be done in polynomial time. Thus, we get the
following theorem.

###### Theorem 2.1

For any set $R$ of red points and $B$ of blue points on $y=0$ with $|R|=|B|$,
there always exists a non-crossing Hamiltonian path whose edges are circular
arcs that lie above or below $y=0$. Moreover, such a path can be computed in
polynomial time.

###  2.2 A Linear Time Algorithm for Non-Crossing Hamiltonian Path

Recall that all the input points lie on $H:y=0$. We assume that the points are
given in sorted order w.r.t their $x$ coordinates. For a point $p$ (except the
last one), let $S(p)$ be the point which is the successor of $p$ in this
order. We use the following algorithm to compute a non-crossing Hamiltonian
path. The algorithm processes the points from left to right and extends the
Hamiltonian path constructed so far by connecting the current point with an
appropriately chosen point. In particular, in every iteration, we consider a
point $p$ and connect it by adding one or more edges. Initially, $p$ is the
leftmost point, and all points are active. We store the constructed path in a
set of edges $\Pi$, which is initially empty.

  * •

Let $l(r)$ and $l(b)$ be the rightmost (or last in the order) red and blue
points, respectively, which are active.

  * •

If the color of $p$ is different from the color of $S(p)$, we simply add a
small arc $(p,S(p))$ to $\Pi$ that lie above $H$. Make $p$ inactive.

  * •

Otherwise, there are two cases.

    1. (i).

If $p$ is red, add two edges $(p,l(b))$ and $(l(b),S(p))$ to $\Pi$. These two
edges are drawn above $H$ as circular arcs. Make $p$ and $l(b)$ inactive.

    2. (ii).

If $p$ is blue, add two edges $(p,l(r))$ and $(l(r),S(p))$ to $\Pi$. These two
edges are drawn below $H$ as circular arcs. Make $p$ and $l(r)$ inactive.

  * •

If $S(p)$ is active, assign $S(p)$ to $p$ (i.e., $p\leftarrow S(p)$) and
repeat all the steps. Otherwise, terminate the algorithm.

The different iterations of the above algorithm are shown in an example in
Figure 6. Now we discuss the correctness of the algorithm. First, we have the
following observation.

Figure 6: Figure showing the execution of the Hamiltonian path computation
algorithm on an example point set.

###### Observation 3

Consider any iteration of the algorithm. Then, any red point on the right of
$l(r)$ (if any) is inactive and has degree 2. Similarly, any blue point on the
right of $l(b)$ (if any) is inactive and has degree 2. Moreover, any point on
the left of $p$ (if any) is inactive and except the first point all of them
have degree 2.

###### Lemma 4

The algorithm correctly computes a bichromatic Hamiltonian path.

###### Proof

Note that when the algorithm terminates, $S(p)$ is inactive. Thus, its degree
must be 2. If $S(p)$ is red (resp. blue), then it had become $l(r)$ (resp.
$l(b)$) at some point and its degree is 2. By Observation 3, all the points
whose colors are same as the color of $S(p)$ and lie on the right of $S(p)$
have degree 2. Also, the degree of all the points on the left of $p$ except
the first point is 2. It is easy to see that the degree of $p$ and the first
point is 1. As the number of red and blue points are same, all the points that
lie on the right of $S(p)$ must have degree 2. Thus, $\Pi$ is a valid
bichromatic Hamiltonian path. ∎

Next, we argue that the computed Hamiltonian path is non-crossing. It is easy
to see that the small arcs added in the second step do not cross any other
drawn edges. Also, the edges drawn above $H$ do not cross any edges drawn
below $H$. Moreover, the edges $(p,l(r))$ and $(l(r),S(p))$ (or $(p,l(b))$ and
$(l(b),S(p))$) drawn in the same iteration do not cross each other. The
following observation completes the claim.

###### Observation 5

Consider two edges $(u,v)$ and $(u^{\prime},v^{\prime})$ which are drawn as
circular arcs above (resp. below) $H$ and added to $\Pi$ in different
iterations. Then, either $u,v$ lie in between $u^{\prime}$ and $v^{\prime}$,
or $u^{\prime},v^{\prime}$ lie in between $u$ and $v$.

The algorithm can be implemented to run in linear time. This is because, one
can use three pointers to keep track of $p$, $l(r)$ and $l(b)$, and these
pointers move in one direction – either from left to right or from right to
left.

###### Theorem 2.2

For any set $R$ of red points and $B$ of blue points on $y=0$ with $|R|=|B|$,
a non-crossing Hamiltonian path can be computed in linear time whose edges are
circular arcs that lie above or below $y=0$.

##  3 Minimum Spanning Tree for Collinear Points

###### Definition 3

Spanning tree for collinear points. Given a set of $n$ red points and a set of
$n$ blue points all of which lie on the line $y=0$, find a minimum weight
geometric tree $T$ in the plane such that each edge of $T$ is represented by a
circular arc that lies above $y=0$, each arc connects a red and a blue point,
and $T$ spans all the input points. The weight of an arc is given by the
Euclidean distance of its endpoints. In the non-crossing version of the
problem, one would like to compute such a tree so that the corresponding
circular arcs are non-crossing.

First, we discuss a greedy linear time algorithm for computing an optimum,
i.e., minimum-weight spanning tree, which potentially has crossings.

###  3.1 Spanning Tree with Crossing

Let $p_{1},\ldots,p_{2n}$ be the input points sorted in increasing order of
their values. We assume that the points are given in this order. Our algorithm
has two steps. In the first step, we traverse the points in the sorted order
and connect each point with its nearest opposite color point using an arc.
This gives us a set of components $\\{C_{1},\ldots,C_{m}\\}$ for $m\in[n]$,
where each component contains at least one edge. For any component
$C_{i},\forall i\in[m]$, let $l(C_{i})$ and $r(C_{i})$ be the leftmost and the
rightmost point, respectively. In the second step, we traverse the components
from left to right. Consider the first two components $C_{1}$ and $C_{2}$. If
$col(r(C_{1}))\neq col(l(C_{1}))$, join $C_{1}$ and $C_{2}$ by an arc
$(r(C_{1}),l(C_{2}))$. Otherwise, check the distance between $r(C_{1})$ and
its nearest opposite color point in $C_{2}$, and the same for $l(C_{2})$ and
its nearest opposite color point in $C_{1}$. Choose the shorter one to join
$C_{1}$, and $C_{2}$. We repeat the same process for each consecutive pair of
the remaining components.

Figure 7: Figure demonstrating the execution of the algorithm on an example.
The dashed arcs are added in the second step.

Note that after the first step each component $C_{i}$ is a tree. In the second
step, we add exactly one edge between a consecutive pair of components. Hence,
the selected arcs form a valid spanning tree. The optimality of the solution
follows from the next observation which is not hard to verify.

###### Observation 6

Cut property: Any edge (or arc) added by the algorithm is a minimum weight
bichromatic cut edge for some cut.

We note that our algorithm does not require the assumption $|R|=|B|$.

###### Theorem 3.1

For any set $R$ of red points and $B$ of blue points on $y=0$, an optimum
spanning tree can be computed in linear time.

Next, we discuss the algorithm for the non-crossing case.

###  3.2 Non-crossing Spanning Tree

Let $P_{1},P_{2},\ldots,P_{m}$ be the alternating monochromatic chunks of
points ordered from left to right for $m\in[n]$. Thus, the color of the points
in $P_{i}$ is different from the color of the points in $P_{i+1}$ for all
$1\leq i\leq m-1$. We start with the following observation.

###### Observation 7

Consider a point $p\in P_{i}$. If an arc $(p,q)$ is contained in a minimum
spanning tree, then either $q\in P_{i-1}$ or $q\in P_{i+1}$.

The observation follows from the idea that if a point is connected to a point
that belongs to a non-consecutive chunk, then one can find a cheaper spanning
tree by replacing the connecting arc with another arc having lower weight. As
the spanning tree we want to compute is non-crossing, by the above
observation, it follows that all the arcs between two consecutive chunks are
nested.

###### Observation 8

Consider any two arcs $(p_{1},q_{1})$ and $(p_{2},q_{2})$ in a minimum non-
crossing spanning tree such that $p_{1},p_{2}\in P_{i}$ and $q_{1},q_{2}\in
P_{i+1}$. Then, either $p_{1}<p_{2}<q_{2}<q_{1}$ or $p_{2}<p_{1}<q_{1}<q_{2}$.

The above observation implies that the outermost arcs between consecutive
chunks form a path (an umbrella) between the first and the last point and all
the other arcs lie inside this umbrella (see Figure 8). Next, we give a simple
algorithm to compute an optimum spanning tree inside such an outermost arc.
Suppose $p_{0},p_{1},\ldots,p_{l},\ldots,p_{k+1}$ be points in sorted order
such that $\\{p_{0},p_{1},\ldots,p_{l}\\}\subseteq P_{i}$ and
$\\{p_{l+1},\ldots,p_{k+1}\\}\subseteq P_{i+1}$. We would like to construct an
optimum spanning tree of the points $p_{0},p_{1},\ldots,p_{l},\ldots,p_{k+1}$
which contains the arc $(p_{0},p_{k+1})$. Our algorithm is based on the
following observation.

Figure 8: Figure showing a spanning tree with the umbrella shown by dashed
arcs.

###### Observation 9

Any optimum spanning tree that contains $(p_{0},p_{k+1})$ must also contain
either $(p_{0},p_{k})$ or $(p_{1},p_{k+1})$ whichever has lower weight.

In our algorithm, we select the shorter arc among $(p_{0},p_{k})$ and
$(p_{1},p_{k+1})$. Then, we recursively solve the problem inside the selected
arc by treating it as an outermost arc. It is easy to see that this problem
can be solved in linear time. Next, we give an algorithm for deciding which
outermost arcs to choose.

Let $p_{1},p_{2},\ldots$ be the input points. Our algorithm incrementally
computes a non-crossing spanning tree starting from the left and by connecting
a new point in each step. Let $P_{1}=\\{p_{1},\ldots,p_{l}\\}$ and
$P_{2}=\\{p_{l+1},\ldots,p_{k}\\}$. To initialize, for each $l+1\leq j\leq k$,
we compute the cost of optimum spanning tree of $\\{p_{1},\ldots,p_{j}\\}$
that contains the outermost arc $(p_{1},p_{j})$ using the above algorithm.
Now, suppose we want to connect a new point $p_{i}\in P_{t+1}$ for $t\geq 2$.
We have already computed the cost of an optimum spanning tree of
$\\{p_{1},\ldots,p_{q}\\}$ with any valid outermost arc $(r,s)$, where $r\in
P_{t-1}$ and $s\in P_{t}$. In the new spanning tree, $p_{i}$ must be connected
to a point $s$ of $P_{t}$. For each such $s$, we compute the cost of the
spanning tree that contains the arc $(s,p_{i})$. In particular, the total cost
is the sum of three costs: (i) the cost of $(s,p_{i})$, (ii) the cost of
connecting the points inside $(s,p_{i})$ and (iii) the cost of the optimum
spanning tree of $p_{1},\ldots,s$ that contains $(r,s)$ for some $r\in
P_{t-1}$. We select the arc $(r,s)$ in our spanning tree that minimizes the
total cost.

Note that each step of this dynamic programming based algorithm takes linear
time. Thus, the optimum spanning tree can be computed in quadratic time.

###### Theorem 3.2

For any set $R$ of red points and $B$ of blue points on $y=0$, an optimum non-
crossing spanning tree can be computed in quadratic time.

##  4 Minimum Non-crossing Matching for Collinear Points

Note that the fact that a minimum weight bichromatic matching for points in
general position is always non-crossing might not hold in the case of
collinear points. Indeed, there are point sets for which no non-crossing
matching exists if the edges are represented by segments. However, one can
show that there is always a non-crossing matching of collinear points such
that each matched edge is a circular arc drawn above the line. Again the
weight of an arc is the Euclidean distance between its endpoints.

###### Definition 4

Non-crossing matching for collinear points. Given a set of $n$ red points and
a set of $n$ blue points all of which lie on the line $y=0$, find a set of $n$
non-crossing circular arcs in the plane of minimum total weight such that the
arcs lie above $y=0$, each arc connects a red and a blue point, and the arcs
span all the input points.

Using the bipartite matching algorithm due to Kaplan et al. [14] along with a
simple postprocessing (already described in the introduction), one can
immediately solve this problem in $O(n^{2}\operatorname{poly}(\log n))$ time.
Here we design a simple algorithm with improved $O(n)$ time complexity.

Let $p_{1},p_{2},\ldots,p_{2n}$ be the input points sorted from left to right
based on their $x$ coordinates. We assume that the points are given in this
order. For any point $p_{i}\in P$, let $col(p_{i})$ denote the color of
$p_{i}$. A subset of points $P_{i}\subseteq P$ is called _color-balanced_ if
it contains an equal number of red and blue points. We traverse the points
from left to right and seek for the first balanced subset (denoted by
$P_{1}$). In order to obtain $P_{1}$ we use a simple method. We start with the
leftmost point $p_{1}$ and maintain a counter $C$ which is used to find the
balanced subset and is initialized to $0$ at the beginning. If $col(p_{1})=$
red, we increase the value of $C$ by $1$, and decrease by $1$, otherwise.
Observe that we will get a balanced subset when the value of $C$ becomes $0$.
Let $P_{1}\subseteq P$ be the first balanced subset containing $2m$ (for some
$m\in[n]$) points. The remaining points $P\setminus P_{1}$ also form a
balanced subset since $P$ contains exactly $n$ red and $n$ blue points. We
prove the following lemma.

###### Lemma 10

Let $P_{1}\subseteq P$ be the first color-balanced subset of $P$ and
$|P_{1}|=2m$. Then $col(p_{1})\neq col(p_{2m})$, and any minimum non-crossing
perfect matching $M_{P}$ of $P$ contains the edge $(p_{1},p_{2m})$.

###### Proof

The first part of the lemma is clearly true, otherwise the value of the
counter would not be $0$ at $p_{2m}$, which is the termination criteria to
obtain the first balanced subset. Now, let us assume that $M_{P}$ does not
contain the edge $(p_{1},p_{2m})$. Then one of the following two situations
can happen: 1) $p_{1}$ and $p_{2m}$ are matched with two intermediate points
from $P_{1}$; 2) one or both of $p_{1}$ and $p_{2m}$ are matched with points
from $P\setminus P_{1}$.

#### Case $1$:

$p_{1}$ and $p_{2m}$ are matched with two intermediate points $p_{k}$ and
$p_{\ell}$, respectively. Note $\ell>k$, otherwise the matched edges cross
each other. We know that $\\{p_{1},\ldots,p_{k}\\}$ is not a balanced subset
since $P_{1}$ is the first balanced subset. Therefore, there exists at least
one point $p_{r}$ (where $1<r<k$) that is matched with a point $p_{s}$ (where
$s>k$). In that case, the edge $(p_{r},p_{s})$ will intersect $(p_{1},p_{k})$.
Hence, we get a contradiction.

#### Case $2$:

Suppose both of $p_{1}$ and $p_{2m}$ are matched with points from $P\setminus
P_{1}$ and no other point from $\\{p_{2},\ldots,p_{2m-1}\\}$ is matched with
any point from $P\setminus P_{1}$. Then we can construct a new matching by
adding the edge $(p_{1},p_{2m})$ and by matching the two points in $P\setminus
P_{1}$. The new matching has lesser cost and is non-crossing; see Figure 9(a).
If any other point in $\\{p_{2},\ldots,p_{2m-1}\\}$ (say $p_{x}$) is also
matched with a point in $P\setminus P_{1}$, then we know it must be of
opposite color of either $p_{1}$ or $p_{2m}$, since $col(p_{1})\neq
col(p_{2m})$. Hence, we can either give the edge $(p_{1},p_{x})$ or
$(p_{x},p_{2m})$ and this reduces the total cost; see Figure 9 (b). The new
matching might not be non-crossing. But, using similar argument one can remove
all the crossings without increasing the cost. Thus, at the end we get a
cheaper non-crossing matching, which contradicts the optimality of $M_{P}$.

Figure 9: Figure demonstrating the two situations in the case when both
$p_{1}$ and $p_{2m}$ are matched with points from $P\setminus P_{1}$.

Now, if only one of $p_{1}$ or $p_{2m}$ is matched (WLOG, assume it is
$p_{1}$) with a point from $P\setminus P_{1}$, then we know there must be at
least one other point (say $p_{x}\in P_{1}$) that is also matched with a point
from $P\setminus P_{1}$, and $col(p_{1})\neq col(p_{x})$. We can apply similar
arguments as above to get a contradiction, which concludes the proof of the
lemma. ∎

Now, we use Lemma 10 to proceed with the algorithm. First, we obtain the
balanced subset $P_{1}$, and match the points $p_{1}$ and $p_{2m}$ by an arc
and include the edge $(p_{1},p_{2m})$ in $M_{P}$. This edge partitions the
point set into subsets, i.e., $P_{2}=P\setminus P_{1}$ and
$P^{\prime}_{1}=P_{1}\setminus\\{p_{1},p_{2m}\\}$. On each of these subsets we
recursively perform the same procedure. This process is repeated until each
point of $P$ is matched.

Due to Lemma 10, we know that every edge we choose in our algorithm must be
part of the optimum solution, and no two edges cross each other. It is not
hard to see that all the balanced subsets can be computed in linear time in
advance, as they are corresponding to matched parentheses and are at most $n$
in number333This algorithm can be easily implemented in the following manner.
Consider the points in left to right order, and insert the leftmost point
($p_{1}$) into a stack. Now, if the next point $p_{2}$ is of same color as
$p_{1}$ then insert $p_{2}$ into the stack, otherwise match $p_{1},p_{2}$ and
remove $p_{1}$ from the stack. Repeat this process until all points are
considered.. Thus, we conclude with the following theorem.

###### Theorem 4.1

For any set $R$ of red points and $B$ of blue points on $y=0$ with $|R|=|B|$,
an optimum non-crossing matching can be computed in linear time.

##  5 TS Tour for Chunked Points on a Circle

Finally, we study the Traveling Salesman problem on the following special
point configuration on a circle.

###### Definition 5

TS tour for chunked points on a circle. We are given a set of $n$ red points
and a set of $n$ blue points all of which lie on a fixed circle. All points
are distributed equidistantly on the circle. Further, the input points are
divided into alternately-colored _chunks_ , where each chunk contains exactly
$k$ consecutive points of the same color. The goal is to find a geometric
(closed) tour $\pi$ in the plane of minimum total length such that $\pi$
consists of segments each of which connects a red and a blue point and $\pi$
spans all the input points.

Figure 10: Figure demonstrating the point configuration we consider for TS
tour, where $n=8$ and $k=4$.

Note that by definition, $n/k$ is an integer. The total number of chunks is
$L=2n/k$ of which $n/k$ contain only red points and $n/k$ contain only blue
points. The configuration of the points mentioned in the above definition is
shown in Figure 10 with an example. For any arc between two points $u$ and $v$
on the circle $C$, we denote the arc by $c(uv)$ (resp. $a(uv)$) if it is the
clock (resp. anticlock) -wise traversal from $u$ to $v$ along $C$. As any two
consecutive points are a fixed distance apart we measure the length of any
bichromatic edge (a straight line segment) $uv$ by the minimum of the number
of points on the arcs $c(uv)$ and $a(uv)$, respectively (including $u$ and
$v$). Next, we design an algorithm for computing a TS tour for the input
points. We consider two cases: (i) $k$ is even and (ii) $k$ is odd.

####  _$(i)$ $k$ is Even_.

The algorithm in this case is as follows.

#### _1._

Let $2p=k$. Partition each chunk into two subchunks each containing $p$
consecutive points. Merge all consecutive subchunks of different colors to
form groups. Note that each group contains $p$ red and $p$ blue points. We
still preserve the geometry of the points of each group and identify the two
peripheral red and blue points of each group as special points. We first
compute a bichromatic path between the two special points for each group and
later connect the special points of different groups to construct a TS tour
for all the points.

#### _2._

For each group, we compute the TS tour in the following way. Consider the
ordering of the groups w.r.t clockwise traversal of the points and consider
the $i^{th}$ group in this order. WLOG, assume that the red points are visited
before the blue points while traversing the points of the group in clockwise
order. Let
$r_{1}^{i},r_{2}^{i},\ldots,r_{p}^{i},b_{p}^{i},b_{p-1}^{i},\ldots,b_{1}^{i}$
be the points in this order. Join $r_{p}^{i}$ with $b_{p}^{i}$ and
$b_{p-1}^{i}$ using two edges. For each $p-1\geq j\geq 2$, join $r_{j}^{i}$
with $b_{j+1}^{i}$ and $b_{j-1}^{i}$. Finally, join $r_{1}^{i}$ with
$b_{2}^{i}$ (see Figure 11). Note that each of the points in the group except
$r_{1}^{i}$ and $b_{1}^{i}$ is connected to two points. $r_{1}^{i}$ and
$b_{1}^{i}$ are connected to only one point.

#### _3._

Next, we connect the special points of different groups. Recall that $L$ is
the total number of groups. Let for the first group the red points are visited
before the blue points while traversing the points of the group in clockwise
order. Note that the special points are
$r_{1}^{1},b_{1}^{1},b_{1}^{2},r_{1}^{2},r_{1}^{3},b_{1}^{3},\ldots,b_{1}^{L},r_{1}^{L}$.
For $1\leq i\leq L-1$, we connect $r_{1}^{i}$ to $b_{1}^{i+1}$. We also
connect $r_{1}^{L}$ to $b_{1}^{1}$ (see Figure 11).

Figure 11: An example of the tour computation for the even case. The edges
between points of same (resp. different) groups are shown using regular (resp.
dashed) segments.

It is not hard to see that the set of selected edges form a valid traveling
salesman tour. This is because each of the points is connected to exactly two
other points of opposite color. Now, we give a bound on the length of the
tour.

###### Lemma 11

The length of the computed tour is $n(k+2+2/k)$.

###### Proof

Note that we have added two types of edges (1) between points of same group,
and (2) between the special points. The length of an edge of the second type
is exactly $k+1$, and the number of those edges is $L$. For each group, we
have $k-1$ type 1 edges whose total length is,

$\displaystyle 2+(3+3)+(5+5)+\ldots+(k-1+k-1)$ $\displaystyle=$ $\displaystyle
2\cdot(1+3+\ldots+k-1)$ $\displaystyle=$ $\displaystyle
2\cdot(k^{2}/4)=k^{2}/2$

Thus, for all the groups, the total length of the type 1 edges is $Lk^{2}/2$.
Hence, the total length of all edges is $L((k^{2}+2k+2)/2)=n(k+2+2/k)$. ∎

The algorithm for the odd case is as follows.

  1. 1.

Let $2p+1=k$. Partition each chunk without the middle point into two subchunks
each containing $p-1$ consecutive points. Add the middle point to both
subchunks. Merge all consecutive subchunks of different colors to form groups.
Note that each group contains $p$ red and $p$ blue points. We still preserve
the geometry of the points of each group and identify the two peripheral red
and blue points as special points. For each group, We compute a bichromatic
path between the two special points. As each pair of consecutive groups share
a special point, the union of the paths corresponding to the groups form a
valid tour.

  2. 2.

For each group, we compute the TS tour exactly in the same way as in the $k$
is even case.

Figure 12: An example of the tour computation for the odd case.

Now, we give a bound on the length of the tour.

###### Lemma 12

The length of the computed tour is $n(k+2+1/k)$.

###### Proof

For each group, we have $k$ edges whose total length is,

$\displaystyle 2+(3+3)+(5+5)+\ldots+(k+k)$ $\displaystyle=$ $\displaystyle
2\cdot(1+3+\ldots+k)$ $\displaystyle=$ $\displaystyle(k+1)^{2}/2$

Thus, for all the groups, the total length of the edges is
$(2n/k)\cdot((k^{2}+2k+1)/2)=n(k+2+1/k)$. ∎

Note that the algorithm can be easily implemented in linear time assuming the
points are given in clockwise or anticlockwise order.

###  5.1 Lower Bound

###### Lemma 13

The length of any bichromatic traveling salesman tour for the configuration of
the points on the circle is at least $n(k+2+2/k)$ if $k$ is even and at least
$n(k+2+1/k)$ if $k$ is odd.

###### Proof

Assume $k$ is even. The odd case can be handled in a similar way. We will show
that the weight of the edges adjacent to each red chunk is at least
$k^{2}+2k+2$ in any tour. As the edges adjacent to two distinct red chunks are
disjoint, and the number of red chunks is $n/k$ the lemma follows. Consider a
fixed red chunk. The $k$ red points in the chunk must be connected to blue
points with $2k$ distinct edges. WLOG, we assume that the only blue points
with which these $k$ points are connected are the $2k$ blue points of the two
adjacent chunks. Partition the red chunk into two subchunks each containing
$k/2$ consecutive points. Again WLOG, we can assume that the points of a
subchunk are only connected to the blue points of the adjacent chunk. Now,
consider a fixed subchunk. Note that the $k/2$ points should have a total of
degree $k$ which will come from the $k$ blue points. Also each blue point can
be connected to only two red points. If the degree $k$ come from only $k/2$
blue points, then the subtour involving the $k/2$ red and $k/2$ blue points
form a cycle. Hence, the $k/2$ red points connect to at least $k/2+1$ blue
points. Also it is beneficial to connect the red points to the closest $k/2+1$
blue points among the points of the blue chunk. Moreover, to satisfy a total
degree $k$ from these $k/2+1$ blue points, it is always beneficial to have
only one degree from the farthest and the second farthest blue points, and two
degree from each of the remaining $k/2-1$ points.

Now, there cannot be the case that the first red point $r_{1}$ (adjacent to
the blue chunk) gets connected to the farthest and the second farthest blue
points. Otherwise, the remaining $k/2-1$ red and $k/2-1$ blue points will form
a cycle. Thus, at most one among the farthest and the second farthest blue
points gets connected to $r_{1}$. The cost to connect the farthest blue point
is at least $k/2+2$. The edges that connect the remaining $k/2$ blue points
and $k/2$ red points form a path between the second farthest blue point and a
red point. The idea is to prove that the cost to connect these points is at
least $(k^{2}+k-2)/2$. Thus, the total cost is at least $(k^{2}+2k+2)/2$ for
one red subchunk. For both red subchunks the cost is $k^{2}+2k+2$, and thus
the lemma follows. ∎

###### Theorem 5.1

For any set $R$ of red points and $B$ of blue points on a circle with
$|R|=|B|$, an optimum non-crossing TS tour can be computed in linear time.

##  6 Conclusion and Open Problems

In this paper, we have studied four classical graph problems on geometric
graphs induced by bichromatic points in two restricted settings: (i) collinear
points and (ii) equidistant points on a circle. We have shown that almost all
of these problems can be solved in linear time in these settings. For the case
of collinear points, the results are obtained for graphs whose edges can be
drawn as circular arcs. We note that the results for collinear points and
circular-arc edges trivially extend to other types of edges drawn
topologically equivalent within the same halfplane, e.g, 1-bend polylines. One
problem that is left open by our work is to decide the complexity of
Bichromatic TSP for collinear points. Also, it would be nice to extend our
result for chunked points to any configuration of points on a circle.

## References

  * [1] A. K. Abu-Affash, A. Biniaz, P. Carmi, A. Maheshwari, and M. H. M. Smid.  Approximating the bottleneck plane perfect matching of a point set.  Comput. Geom., 48(9):718–731, 2015.
  * [2] P. K. Agarwal, A. Efrat, and M. Sharir.  Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications.  SIAM J. Comput., 29(3):912–953, 1999.
  * [3] S. Anily and R. Hassin.  The swapping problem.  Networks, 22(4):419–433, 1992.
  * [4] S. Arora.  Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems.  J. ACM, 45(5):753–782, 1998.
  * [5] F. Bernhart and P. C. Kainen.  The book thickness of a graph.  J. Combinatorial Theory, Series B, 27(3):320–331, 1979.
  * [6] A. Biniaz, P. Bose, A. Maheshwari, and M. H. M. Smid.  Plane geodesic spanning trees, Hamiltonian cycles, and perfect matchings in a simple polygon.  Comput. Geom., 57:27–39, 2016.
  * [7] A. Biniaz, P. Bose, A. Maheshwari, and M. H. M. Smid.  Plane bichromatic trees of low degree.  Discrete & Computational Geometry, 59(4):864–885, 2018.
  * [8] M. G. Borgelt, M. J. van Kreveld, M. Löffler, J. Luo, D. Merrick, R. I. Silveira, and M. Vahedi.  Planar bichromatic minimum spanning trees.  J. Discrete Algorithms, 7(4):469–478, 2009.
  * [9] W. S. Evans, G. Liotta, H. Meijer, and S. K. Wismath.  Alternating paths and cycles of minimum length.  Comput. Geom., 58:124–135, 2016.
  * [10] A. Frank, E. Triesch, B. Korte, and J. Vygen.  On the bipartite travelling salesman problem.  1998\.
  * [11] A. Kaneko and M. Kano.  Straight-line embeddings of two rooted trees in the plane.  Discrete & Computational Geometry, 21(4):603–613, 1999.
  * [12] A. Kaneko and M. Kano.  Discrete geometry on red and blue points in the plane—a survey—.  In Discrete and computational geometry, pages 551–570. Springer, 2003.
  * [13] A. Kaneko, M. Kano, and K. Suzuki.  Balanced partitions and path covering of two sets of points in the plane.  preprint.
  * [14] H. Kaplan, W. Mulzer, L. Roditty, P. Seiferth, and M. Sharir.  Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications.  In Symposium on Discrete Algorithms, SODA 2017, pages 2495–2504, 2017.
  * [15] J. Kyncl, J. Pach, and G. Tóth.  Long alternating paths in bicolored point sets.  Discrete Mathematics, 308(19):4315–4321, 2008.