# A simple, passive design for large optical trap arrays for single atoms

P. Huft<EMAIL_ADDRESS>Department of Physics, University of Wisconsin-Madison,
1150 University Avenue, Madison, WI 53706  Y. Song  Department of Physics,
University of Wisconsin-Madison, 1150 University Avenue, Madison, WI 53706  T.
M. Graham  Department of Physics, University of Wisconsin-Madison, 1150
University Avenue, Madison, WI 53706  K. Jooya  Department of Physics,
University of Wisconsin-Madison, 1150 University Avenue, Madison, WI 53706  S.
Deshpande  C. Fang  M. Kats  Department of Electrical and Computer
Engineering, University of Wisconsin-Madison, 1415 Engineering Drive, Madison,
WI 53706  M. Saffman  Department of Physics, University of Wisconsin-Madison,
1150 University Avenue, Madison, WI 53706  ColdQuanta, Inc., 111 N. Fairchild
St., Madison, WI 53703

# A simple, passive design for large optical trap arrays for single atoms

P. Huft<EMAIL_ADDRESS>Department of Physics, University of Wisconsin-Madison,
1150 University Avenue, Madison, WI 53706  Y. Song  Department of Physics,
University of Wisconsin-Madison, 1150 University Avenue, Madison, WI 53706  T.
M. Graham  Department of Physics, University of Wisconsin-Madison, 1150
University Avenue, Madison, WI 53706  K. Jooya  Department of Physics,
University of Wisconsin-Madison, 1150 University Avenue, Madison, WI 53706  S.
Deshpande  C. Fang  M. Kats  Department of Electrical and Computer
Engineering, University of Wisconsin-Madison, 1415 Engineering Drive, Madison,
WI 53706  M. Saffman  Department of Physics, University of Wisconsin-Madison,
1150 University Avenue, Madison, WI 53706  ColdQuanta, Inc., 111 N. Fairchild
St., Madison, WI 53703

###### Abstract

We present an approach for trapping cold atoms in a 2D optical trap array
generated with a novel $4f$ filtering scheme and custom transmission mask
without any active device. The approach can be used to generate arrays of
bright or dark traps, or both simultaneously with a single wavelength for
forming two-species traps. We demonstrate the design by creating a 2D array of
1225 dark trap sites, where single Cs atoms are loaded into regions of near-
zero intensity in an approximately Gaussian profile trap. Moreover, we
demonstrate a simple solution to the problem of out-of-focus trapped atoms,
which occurs due to the Talbot effect in periodic optical lattices. Using a
high power yet low cost spectrally and spatially broadband laser, out-of-focus
interference is mitigated, leading to near perfect removal of Talbot plane
traps.

##  I Introduction

Optical trap arrays are a key ingredient in neutral atom based quantum
technologies, including quantum computing, quantum simulation, and quantum
sensing, due to their stability and versatility [1, 2]. This is the result of
advances over the past two decades in creating low-entropy arrays of single
atoms, which have made optical trap arrays ubiquitous in quantum science.
However, the optical setups for creating these traps are often complicated,
space-consuming, and expensive, requiring active electro-optical devices such
as liquid crystal spatial light modulators (SLMs)[3], acousto-optic deflectors
(AODs)[4], and digital micromirror devices (DMDs)[5]. In response to this
experimental overhead, we propose a simple method of creating optical trap
arrays using only passive components, consisting of a mask with a custom
transmission pattern and a $4f$ imaging setup with a Fourier plane iris for
spatial filtering.

Two major advantages exist for optical traps created with passive rather than
active components: 1) passive components are free from noise associated with
active devices, such as intensity flicker which can lead to short trap
lifetimes [6], and 2) they have the capability to handle high optical powers
which enables scaling to very large trap arrays. The approach we demonstrate
uses a passive amplitude mask, which has some advantages over a passive
hologram. Specifically, an amplitude mask can be used with a broad range of
wavelengths, and can also be used with incoherent light, which we show can be
used for mitigating the Talbot effect for periodic trap arrays. We show how
the same basic working principle can be used to create both bright and dark
traps, where atoms are trapped in regions of high and low intensity,
respectively. Moreover, this approach can be used to create a dual-grid of
both dark and bright traps for confining two different atomic species[7] using
only one passive optical mask and a single trapping wavelength. We show as a
proof of principle the creation of a two-dimensional 1225-site array which is
used for trapping single Cs atoms in blue-detuned dark traps. Several other
recent experiments have demonstrated large atom arrays [5, 8, 9]. However, all
of these relied on active devices. A microlens array can be used to create an
array of red-detuned bright traps without requiring any active devices[10],
but cannot be easily extended to the dark and bright-dark arrays described
here.

The paper is organized as follows. In sec. II, the working principle is
discussed for creating an array of bright red-detuned traps, dark blue-detuned
traps, or a combination of the two. In sec. III, we discuss an experimental
demonstration of trapping single Cs atoms in a dark trap array, and show that
the Talbot effect can be mitigated by using incoherent trap light.

##  II Working Principle

###  II.1 Bright Trap Array

Here we discuss the case of creating an array of bright optical dipole traps,
in which atoms are trapped in regions of maximum intensity for light which is
far-detuned red of an atomic transition. Consider a plane wave, incident on an
opaque mask with a fully transmitting aperture of radius $a$ (Fig. 1). If the
illuminated mask is placed in the front focal plane of a lens $f_{1}$, the
field in the back focal plane is the familiar Airy disk, which is the Fourier
transform of the top hat profile of the field just after the mask. Because the
Fourier plane field gives the spatial frequency spectrum of the front focal
plane field, we can reason that filtering out higher spatial frequencies from
the Airy disk will have the effect of creating a low-passed top hat beam after
a second lens transformation.

Figure 1: Working principle for creating approximately Gaussian (aG) field
profiles using a $4f$ filtering scheme. (a) The design for producing a bright
trap from an approximately Gaussian beam. An input plane wave is apertured by
an opaque mask with a transmitting hole of radius $a$ to create a top-hat
profile. A spatial filter or iris of radius $b$ in the Fourier plane transmits
only the central lobe of the Airy disk. After transforming through lens
$f_{2}$, the output field, $A_{2}$, is an approximately Gaussian (aG) beam.
(b) Dark traps can be produced with a mask which is fully transmitting with a
partially transmitting aperture, for which the output is the aG field
subtracted from a plane wave. (c) Intensity profiles of bright (red) and dark
(blue) traps based on aG beams (solid lines) compared to their Gaussian
(dashed lines) counterparts plotted in terms of the Gaussian waist $w_{0}$ and
Rayleigh range $z_{R}=\pi w_{0}^{2}/\lambda$ for the Gaussian bright trap. The
bright traps are normalized to their respective peak focal plane intensities
and the dark traps are normalized to the asymptotic intensity at large
$\rho_{2},z_{2}$. The inset shows a zoomed in view of the higher order
deviation between the aG and Gaussian beam. The axial ($\rho_{2}=0$) and
radial ($z_{2}=0$) profiles for the bright and dark aG trap are computed
numerically using Fresnel diffraction theory. The pairs of dark and light
solid blue curves have $t_{a}=0.287$, $t_{a}=0$, respectively. For all aG beam
curves, $a=100~{}\mathrm{\mu m}$ and $b=f_{1}x_{1}^{(1)}/ak$, except for the
light blue ($t_{a}=0$) curve, which has $b=f_{1}x_{1}^{(0)}/ak$. The other
simulation parameters are $\lambda=825$ nm, and $w_{0}=0.974(f_{2}/f_{1})a$
and $w_{0}=0.943(f_{2}/f_{1})a$ for the bright and dark Gaussian beams,
respectively. (d) Extension of the $4f$ filtering scheme to produce a 2D grid
of dark traps, using a mask with a grid of apertures with spatial period $d$.
(e) A dual grid of bright and dark traps with a single wavelength can be made
with a mask which has finite background transmission $t_{b}$ populated a grid
of fully transmitting ($t_{a,1}=1$) apertures and a dual grid of apertures
with transmission $t_{a,2}<t_{b}$. (f) Dark trap profiles in the $\rho z$
plane corresponding to the blue and light blue solid curves in (c), normalized
to their respective peak intensities.

Placing an iris of radius $b$ in the Fourier plane to filter the Airy disk and
transform through lens $f_{2}$, the output field in the back focal plane found
from Fresnel diffraction theory is

$A_{2}\left(\rho_{2}\right)=-A_{0}\frac{ak}{f_{2}}\int_{0}^{b}d\rho_{1}J_{0}\left(\frac{\rho_{2}k}{f_{2}}\rho_{1}\right)J_{1}\left(\frac{ak}{f_{1}}\rho_{1}\right).$
(1)

The finite Bessel integral above can be expressed as a power series in $b$
using

$\displaystyle\int_{0}^{b}dzJ_{0}(cz)J_{1}(dz)$ $\displaystyle=$
$\displaystyle\sum_{j=0}^{\infty}\frac{(-1)^{j}}{j!(j+1)!(2j+2)}$
$\displaystyle\times$
$\displaystyle{}_{2}F_{1}\left(-j,-1-j;1;c^{2}/d^{2}\right)b^{2+2j}(d/2)^{1+2j}$

where ${}_{2}F_{1}$ is the hypergeometric function [11]. Taking
$f_{1}=f_{2}=f$ and setting $b=\frac{f}{ak}x_{1}^{(1)}$, where
$x_{1}^{(1)}=3.8317$ is the first zero of $J_{1}$, allows further
simplification. This choice for $b$ corresponds to filtering off the lobes
beyond the central bright spot, constituting a power loss of only 16$\%$. With
these choices, we can then express the intensity in the output plane $I_{2}$,
normalized to the input intensity $I_{0}$, as a power series in $\rho_{2}/a$:

$\frac{I_{2}\left(\rho_{2},z_{2}=0\right)}{I_{0}}=1.97-4.15\left(\frac{\rho_{2}}{a}\right)^{2}+3.92\left(\frac{\rho_{2}}{a}\right)^{4}-\ldots$
(2)

To compute the on-axis expansion of the intensity, we modify the integral in
eq. (1) by setting $\rho_{2}=0$ and including the quadratic phase factor
$\text{exp}\big{(}-i\rho_{1}^{2}z_{2}/2f_{2}^{2}\big{)}$ in the integrand,
where $z_{2}$ is the axial deviation from the back focal plane of the second
lens. Both the radial and axial expansions, renormalized to have peak value of
1, are

$\displaystyle\frac{I_{2}\left(\rho_{2},z_{2}=0\right)}{I_{2}(0,0)}$
$\displaystyle=1-2.11\left(\frac{\rho_{2}}{a}\right)^{2}+1.99\left(\frac{\rho_{2}}{a}\right)^{4}-\ldots$
(3) $\displaystyle\frac{I_{2}(\rho_{2}=0,z_{2})}{I_{2}(0,0)}$
$\displaystyle=1-2.60\frac{z_{2}^{2}}{a^{4}k^{2}}+3.28\frac{z_{2}^{4}}{a^{8}k^{4}}-...$

We will refer to this intensity profile as an approximately Gaussian (aG)
beam. Equating the radial profile to a Gaussian intensity profile
$|A_{G}(\rho_{2})|^{2}=\exp(-2\rho_{2}^{2}/w_{0}^{2}))$ at quadratic order, we
find that the aG beam is, to a very good approximation, a Gaussian beam with
$1/e^{2}$ waist $w_{0}=0.974(f_{2}/f_{1})a$ (Fig. 1).

It is useful to recast the coefficients of the quadratic terms for the radial
and axial expansions of $I_{2}$ in terms of Gaussian beam parameters. This is
useful for seeing how the trap confinement compares to a pure Gaussian optical
trap at lower-order in $\rho,z$, and for ease in modifying common expressions
pertaining to Gaussian optical traps, such as trap frequencies (see eq. (18)).
We already showed that the radial expansion can be fit to a Gaussian with
$w_{0}=0.974a$, so we can then equate the quadratic coefficient of the axial
expansion in eq. (3) to a numerical factor times $1/z_{R}^{2}$, where
$z_{R}=\pi w_{0}^{2}/\lambda$ is the familiar Rayleigh range of a Gaussian
beam. The radial and axial expansions, expressed in terms of Gaussian
parameters up to quadratic order and normalized to the peak intensity
$I_{2}(0,0)$ are

$\displaystyle\frac{I_{2}(\rho_{2},z_{2}=0)}{I_{2}(0,0)}$
$\displaystyle=1-2\left(\frac{\rho_{2}}{w_{0}}\right)^{2}+1.79\left(\frac{\rho_{2}}{w_{0}}\right)^{4}-...$
(4) $\displaystyle\frac{I_{2}(\rho_{2}=0,z_{2})}{I_{2}(0,0)}$
$\displaystyle=1-0.59\left(\frac{z_{2}}{z_{R}}\right)^{2}+0.17\left(\frac{z_{2}}{z_{R}}\right)^{4}-...$

We see that the radial confinement of the bright aG beam is the same as that
of the best-fit Gaussian beam, whereas the axial confinement is looser by
around 30$\%$.

This $4f$ filtering approach to creating an aG beam is readily extended to
create an array of aG beams. For example, a 2D grid of $n\times n$ aG beams
can be generated by making the input mask a 2D square grid of $n\times n$
apertures. The field transmitted through each aperture will be an aG pattern
as derived above, but will appear at position $-\rho_{ij}$ in the output
plane, where $\rho_{ij}$ is the input position of the corresponding aperture.
This is shown for a 2D square array in Fig. 1. Provided the spatial period $d$
of apertures on the mask satisfies $d\gtrsim 3a$, the interference between
adjacent beams will be negligible. The resulting array of traps can then be
re-imaged with relay optics to create small traps suitable for single atom
trapping.

The efficiency of the trap creation is defined as the ratio of peak intensity
of the trap in the output plane to the intensity of the input plane wave
incident on the mask. This is given by $=I_{t}/I_{d}$ where $I_{d}=P/d^{2}$ is
the intensity of an input $d\times d$ unit cell, and
$I_{t}=I_{2}(\rho_{2}=0,z2=0)$, which is simply eq. (2) evaluated at
$\rho_{2}=0,z_{2}=0$. Hence, independent of the aperture radius $a$, the
efficiency is given by

$\epsilon=\frac{I_{t}}{I_{d}}=\frac{I_{2}\left(0,0\right)}{I_{0}}=1.97$ (5)

The meaning of an efficiency greater than unity is that the input light has
been redistributed to form a more localized region of intensity with a profile
suitable for trapping. Note that this value of efficiency assumes equal focal
lengths, $f_{1}=f_{2}$. For unequal focal lengths, $\epsilon$ scales as the
magnification factor for intensity, $(f_{1}/f_{2})^{2}$. The fraction of
optical power transmitted through the $4f$ filtering system is equal to the
fraction of power transmitted through the mask, times the fraction transmitted
through the Fourier filter. This gives $P_{\rm out}/P_{\rm in}=0.84(\pi
a^{2}/d^{2})$. For example, with $d=3a$, $P_{\rm out}/P_{\rm in}=0.29$. As we
will see, the design for creating dark traps is more efficient in terms of
power transmission.

We note that a single array mask can be used with different laser wavelengths
$\lambda$ simply by adjusting the Fourier filter radius $b$.

It is also possible to create tighter trap profiles than those described
above, at the expense of using a more complicated amplitude or phase mask in
the Fourier plane[12]. This is discussed in Appendix B.

###  II.2 Dark Trap Array

The scheme presented above can be modified to produce dark traps, where atoms
are trapped in regions of zero intensity for blue-detuned trap light. Dark
traps are often preferable over bright traps for a number of reasons. For
example, 1) the trapped atoms are insensitive to laser power fluctuations 2)
the trap light can be kept on during experiment sequences involving laser
excitation, which may be untenable in bright traps due to large AC Stark
shifts, and 3) Rydberg states, for which the AC Stark shift is always
positive, can also be trapped[13].

It is possible to form an aG dark trap, in which an atom can be trapped at the
intensity minimum, and axial confinement is provided by the diffraction of the
field out of focus. This can be done with a mask which is somewhat
complementary to that above, having partially transmitting apertures on a
fully transmitting background. Denoting the aperture and background
transmission amplitudes as $t_{a}$ and $t_{b}$, respectively, the field after
transforming to the Fourier plane is

$\displaystyle A_{1}\left(\rho_{1}\right)$ $\displaystyle=$
$\displaystyle-i\frac{A_{0}k}{f_{1}}\bigg{[}t_{a}\int_{0}^{a}d\rho_{0}\,\rho_{0}J_{0}\left(\frac{k\rho_{0}\rho_{1}}{f_{1}}\right)+t_{b}\int_{a}^{\infty}d\rho_{0}\,\rho_{0}J_{0}\left(\frac{k\rho_{0}\rho_{1}}{f_{1}}\right)\bigg{]}$
(6) $\displaystyle=$
$\displaystyle-i\frac{A_{0}k}{f_{1}}\bigg{[}\left(t_{a}-t_{b}\right)\int_{0}^{a}d\rho_{0}\,\rho_{0}J_{0}\left(\frac{k\rho_{0}\rho_{1}}{f_{1}}\right)+t_{b}\int_{0}^{\infty}d\rho_{0}\,\rho_{0}J_{0}\left(\frac{k\rho_{0}\rho_{1}}{f_{1}}\right)\bigg{]}.$

The second term in the square brackets, after filtering in the Fourier plane
and a second lens transformation, gives a plane wave with amplitude
$-t_{b}A_{0}$. The first term gives the same result derived for the field in
eq. (1) multiplied by $t_{a}-t_{b}$, such that the total field is a plane wave
minus an aG near-Gaussian profile. For $f_{1}=f_{2}=f$, the on-axis field in
focus is given by

$A_{2}(0)=-A_{0}\left[t_{b}+\left(t_{a}-t_{b}\right)\left[1-J_{0}\left(\frac{kab}{f}\right)\right]\right]$
(7)

This leads to the condition for the field to be zero

$t_{a}=-t_{b}\frac{J_{0}\big{(}\frac{kab}{f}\big{)}}{1-J_{0}\big{(}\frac{kab}{f}\big{)}}.$
(8)

Choosing $b=\frac{f}{ak}x_{1}^{(1)}$ gives $t_{a}=0.287t_{b}$. For a fully
transmitting background, $\left|t_{b}\right|=1$, which implies an aperture
transmission $T_{a}=\left|t_{a}\right|^{2}=0.082$ to make a dark near-Gaussian
trap with a zero intensity minimum. It should be clear that $f_{1}$ need not
equal $f_{2}$ for this result for the aperture transmission amplitude to hold
true. The sensitivity of this zero intensity condition to the iris radius and
relative phase between $t_{a}$ and $t_{b}$ is discussed in Appendix A.

The radial and axial expansions of the dark aG trap are

$\displaystyle\frac{I_{2}(\rho_{2},z_{2}=0)}{I_{0}}$
$\displaystyle=-1.04\times
10^{-6}\left(\frac{\rho_{2}}{w_{0}}\right)^{2}+1.11\left(\frac{\rho_{2}}{a}\right)^{4}-...$
(9) $\displaystyle\frac{I_{2}(\rho_{2}=0,z_{2})}{I_{0}}$
$\displaystyle=\frac{4.44}{a^{4}k^{2}}z_{2}^{2}-\frac{8.04}{a^{8}k^{4}}z_{2}^{4}+...$

The quadratic term in the radial expansion is very close to zero, and will be
dropped going forward. Following the analogy between the Gaussian and aG
fields, this trap profile is similar to $|1-A_{G}|^{2}$, for which the first
non-vanishing term in the radial expansion at $z_{2}$=0 is quartic. Matching
the quartic term of eq. (9) to that of the Gaussian-based equivalent, we find
$w_{0}=0.943a(f_{2}/f_{1})$, where the focal lengths have been left arbitrary.
Again, we can compare the expansion with a Gaussian-based trap by recasting
the coefficients in terms of Gaussian parameters as was done for the bright
trap:

$\displaystyle\frac{I_{2}(\rho_{2},z_{2}=0)}{I_{0}}$
$\displaystyle=\left(\frac{\rho_{2}}{w_{0}}\right)^{4}-...$ (10)
$\displaystyle\frac{I_{2}(\rho_{2}=0,z_{2})}{I_{0}}$
$\displaystyle=1.01\left(\frac{z_{2}}{z_{R}}\right)^{2}-0.33\left(\frac{z_{2}}{z_{R}}\right)^{4}+...$

The trap profiles from eqs. (4) and (10) are plotted in Fig. 1 alongside their
Gaussian counterparts.

The dark aG trap radial profile in the focal plane is nearly quartic. One
consequence is that the distribution of atoms will therefore be different than
for a harmonic trap, as discussed in section II.4. A trapping potential which
is harmonic to lowest order may be desirable in some cases, for example to
allow for the implementation of sideband cooling [14]. For particular values
of finite $t_{a}$, the traps generated with this design can be made harmonic
by imposing a finite phase difference $\phi_{ab}$ between the transmitting
mask background and choosing a suitable iris radius $b$. This is discussed
further in Appendix D.1.

An attractive modification of the dark aG trap is to use a mask which has
$t_{a}=0$, corresponding to opaque disks on the fully transmitting background
(the complement of the bright trap mask), which may be easier to fabricate
reliably compared to the version requiring a specific finite value for
$t_{a}$. This could be implemented with either a passive optical element or or
an active amplitude spatial light modulator such as a DMD. From the condition
for a dark trap center given in eq. (8), we find that the iris radius should
be set to $b_{n}=(f/ka)x_{n}^{(0)}$, where $x_{n}^{(0)}$ is the $n^{\rm th}$
zero of Bessel $J_{0}$ and $n>0$. In the limit of large $n$, the trap radial
profile approaches a square well of radius $a$, which is simply the re-imaged
mask aperture with no Fourier filtering. For iris radius $b_{1}$ and
$a=w_{0}(f1/f2)/0.943$, the radial and axial trap profiles in terms of
Gaussian beam parameters are given by

$\displaystyle\frac{I_{2}(\rho_{2},z_{2}=0)}{I_{0}}$
$\displaystyle=0.31\left(\frac{\rho_{2}}{w_{0}}\right)^{4}-0.12\left(\frac{\rho_{2}}{w_{0}}\right)^{6}...$
(11) $\displaystyle\frac{I_{2}(\rho_{2}=0,z_{2})}{I_{0}}$
$\displaystyle=0.31\left(\frac{z_{2}}{z_{R}}\right)^{2}-0.03\left(\frac{z_{2}}{z_{R}}\right)^{4}+...$

and shown in Fig. 1.

The efficiency of the dark aG trap for all variations considered is given
approximately by

$\epsilon=\frac{I_{t}}{I_{d}}=\frac{I_{d}}{I_{d}}=1$ (12)

which follows from the fact that the input plane wave is fully transmitted
through the Fourier filter. For the dark traps with $t_{a}=0.287$ and
$t_{a}=0$ shown in Fig. 1, the efficiency is about 1.1 and 1.2, respectively,
due to diffraction effects. For an array of dark traps, this efficiency is
valid when interference between neighboring traps is negligible with $d\gtrsim
6a$. The efficiency of the dark trap variants is lower than for the bright
trap, but compares favorably with dark traps created with a Gaussian beam
array using diffractive optical elements which has $\epsilon\leq 0.51$ [15] or
a line array which has $\epsilon\leq 0.97$. [16].

The fractional power transmission through the $4f$ filtering setup for the
dark trap array is more favorable than that of the bright trap, which has a
mask with an opaque background. For a mask with arbitrary background and
aperture transmissions, we have $P_{\rm out}/P_{\rm
in}=\eta(|t_{b}|^{2}(d^{2}-\pi a^{2})+|t_{a}|^{2}\pi a^{2})/d^{2}$ where
$\eta$ is the fractional transmission of the Fourier filter, which depends on
the optimal filter radius for the choice of $t_{a}$. For $t_{a}=0$,
$\eta=0.73$, found by integrating the Airy disk up to radius $b_{1}$ as
defined above. For a mask with either $|t_{a}|=0$ or $|t_{a}|=0.287$ and
$d=3a$, $P_{\rm out}/P_{\rm in}\approx 0.50$.

Parameter | Gaussian | Bright aG | Dark aG
---|---|---|---
$I(\rho,0)/I(0,0)$ | $1-2\big{(}\frac{\rho}{w_{0}}\big{)}^{2}+2\big{(}\frac{\rho}{w_{0}}\big{)}^{4}-...$ | $1-2\big{(}\frac{\rho}{w_{0}}\big{)}^{2}+1.79\big{(}\frac{\rho}{w_{0}}\big{)}^{4}-...$ |  $\big{(}\frac{\rho}{w_{0}}\big{)}^{4}-...$
$I(0,z)/I(0,0)$ | $1-\big{(}\frac{z}{z_{R}}\big{)}^{2}+\big{(}\frac{z}{z_{R}}\big{)}^{4}-...$ | $1-0.585\big{(}\frac{z}{z_{R}}\big{)}^{2}+0.166\big{(}\frac{z}{z_{R}}\big{)}^{4}-...$ |  $1.01\big{(}\frac{z}{z_{R}}\big{)}^{2}-0.330\big{(}\frac{z}{z_{R}}\big{)}^{4}+...$
$\omega_{\rho}$ | $\frac{2}{w_{0}}\sqrt{\frac{U_{0}}{m}}$ | $\frac{2}{w_{0}}\sqrt{\frac{U_{0}}{m}}$ | ill-defined
$\omega_{z}$ | $\frac{1}{z_{R}}\sqrt{\frac{U_{0}}{m}}$ | $\frac{1}{1.307z_{R}}\sqrt{\frac{U_{0}}{m}}$ |  $\frac{1}{0.997z_{R}}\sqrt{\frac{U_{0}}{m}}$
$\sigma_{\rho}$ |  $w_{0}\big{(}\frac{k_{B}T}{2U_{0}}\big{)}^{1/2}=0.22~{}\mu$m |  $w_{0}\big{(}\frac{k_{B}T}{2U_{0}}\big{)}^{1/2}=0.22~{}\mu$m |  $w_{0}\big{(}\frac{2}{3}\frac{k_{B}T}{U_{0}}\big{)}^{1/4}=0.28~{}\mu$m
$\sigma_{z}$ |  $z_{R}\big{(}\frac{k_{B}T}{2U_{0}}\big{)}^{1/2}=0.87~{}\mu$m |  $1.307z_{R}\big{(}\frac{k_{B}T}{2U_{0}}\big{)}^{1/2}=1.14~{}\mu$m |  $0.997z_{R}\big{(}\frac{k_{B}T}{2U_{0}}\big{)}^{1/2}=0.87~{}\mu$m
Table 1: Comparison of normalized intensity profiles $I$, atom distribution
standard deviations $\sigma$, and vibrational frequencies $\omega$ for the
bright and dark aG ($t_{a}=0.287$) trap potentials, and a standard Gaussian
bright trap. For ease of comparison, the expressions have all been cast in
terms of the best-fit Gaussian waist $w_{0}$ and corresponding $z_{R}$.
Numerical values for the standard deviations are given using $\lambda=808$ nm
and $w_{0}=1~{}\mu$m, and a ratio of atom kinetic energy to trap potential
$k_{B}T/U_{0}=1/10$.

###  II.3 Combined Bright and Dark Trap Array

An interesting application of this technique is a grid of both bright and dark
traps for trapping two atomic species with a single trapping wavelength. There
has been interest in such two-species trap arrays as they have potential
applications for error-corrected quantum computing [17]. While a large array
of Rb and Cs atoms was recently demonstrated [7], the proposed approach
requires only one trapping wavelength and a single passive optical element to
create the intensity pattern for both traps, which simplifies the complexity
of the experimental setup. Such a trap can be made utilizing transitions in
two species which have dynamic polarizabilities of comparable magnitude but
opposite sign for the chosen wavelength.

Consider a mask with a background of transmission $t_{b}$, populated with a
grid of fully-transmitting apertures for bright traps and a dual grid of
apertures with transmission amplitude $t_{a}=0.287t_{b}$ for forming dark
traps, with $\left|t_{a}\right|<\left|t_{b}\right|$ (Fig. 1). The peak
intensity of the bright trap occurs at $(\rho_{2},z_{2})=(0,0)$, and that of
the dark trap occurs off-axis for large $\rho_{2}$, where the intensity is
simply that of the plane wave transmitted through the mask. Assuming
$f_{1}=f_{2}$ for simplicity, and using eq. (7), the peak intensity of the
output bright traps relative to the background intensity, and that of the dark
traps are given by

$\displaystyle I_{\text{bright}}(\rho_{2}=0,z_{2}=0)$ $\displaystyle=$
$\displaystyle\bigg{|}\left(t_{b}-1\right)\left[1-J_{0}\left(x_{1}^{(1)}\right)\right]-t_{b}\bigg{|}^{2}-\left|t_{b}\right|^{2}$
(13) $\displaystyle I_{\rm dark}(\rho_{2}\rightarrow\infty,z_{2}=0)$
$\displaystyle=$ $\displaystyle\left|t_{b}\right|^{2}$ (14)

where $I_{\rm bright}(\rho_{2}=0,z_{2}=0)$ and $I_{\rm
dark}(\rho_{2}\rightarrow\infty,z_{2}=0)$ are found from eqs. (2) and (9),
respectively. These relative intensities are equal for $t_{b}\approx 0.77$.

The condition for one species to be trapped in the bright spots and one in
dark traps, with equal trap depths, is $\left|\alpha_{b}I_{\rm
bright}\right|=\left|\alpha_{d}I_{\rm dark}\right|$. Choosing $\lambda=810$
nm, we can create bright traps for Rb and dark traps for Cs. The dynamic
ground state polarizability at 810 nm for Rb is
$\alpha_{b}=847~{}\textrm{\AA}^{3}$ and for Cs is
$\alpha_{d}=-433~{}\textrm{\AA}^{3}$, from which we obtain $t_{b}=0.86$ to
have equal trap depths for Rb and Cs. For the case of using fully opaque dark
apertures, i.e. $t_{a}=0$, the dark trap efficiency is about 1.2 and we get
$t_{b}=0.84$ for the bright and dark mask. Note that in this case, the dark
apertures should have radius
$a_{\textrm{dark}}=a_{\textrm{bright}}(x_{1}^{(0)}/x_{1}^{(1)})$ so that the
same Fourier filter radius is optimal for both the bright and dark traps.

###  II.4 Atom Confinement

The figures of merit for trapping a particle, such as an atom or molecule, are
the depth of the trapping potential and the spatial confinement of the
particle. Assuming the particle to be in a low energy motional state, we can
approximate the trap as a harmonic potential by keeping only up to the
quadratic terms in spatial coordinates. For a bright trap, where atoms are
trapped at the peak intensity, we have
$U=U_{0}\left(1-\epsilon_{\perp}\rho^{2}-\epsilon_{\|}z^{2}+\ldots\right)$,
where $\rho$ and $z$ are the radial and axial coordinates of the particle,
respectively, and $z$ is along the axis of optical propagation of the trap
light. For a dark trap, where atoms are trapped at the minimum intensity,
$U=U_{0}\left(\epsilon_{\perp}\rho^{2}-\epsilon_{\|}z^{2}+\ldots\right)$.
Because the equations of motion are not affected by constant terms in the
potential, the equations for trap frequencies and confinement that follow are
valid for either bright or dark potentials.

We can obtain the spread in a trapped particle’s position by using the Virial
theorem to relate the potential and kinetic energy of the trapped particle.
For a particle of temperature $T$, the standard deviations of the particle
position are given by

$\displaystyle 2U_{0}\epsilon_{\perp}\left\langle\rho^{2}\right\rangle$
$\displaystyle=2k_{B}T$ (15) $\displaystyle 2U_{0}\epsilon_{\|}\left\langle
z^{2}\right\rangle$ $\displaystyle=k_{B}T$

with $k_{B}$ the Boltzmann constant. The standard deviations of the particle
position are therefore

$\begin{gathered}\sigma_{\rho}=\sqrt{\left\langle\rho^{2}\right\rangle}=\frac{1}{\epsilon_{\perp}^{1/2}}\left(\frac{k_{\mathrm{B}}T}{U_{0}}\right)^{1/2}\\\
\sigma_{z}=\sqrt{\left\langle
z^{2}\right\rangle}=\frac{1}{\left(2\epsilon_{\|}\right)^{1/2}}\left(\frac{k_{\mathrm{B}}T}{U_{0}}\right)^{1/2}\end{gathered}$
(16)

where $k_{B}$ is the Boltzmann constant.

Figure 2: Schematic of the experimental apparatus for trapping laser-cooled
cesium atoms in a dark trap array made with a broadband, spatially multimode
808 nm laser. Atoms are loaded into a magneto-optical trap (MOT), then
transferred into a blue-detuned dark trap array which overlaps the MOT. The
trap array pattern is formed using a passive optical mask and $4f$ filtering
scheme, and the trap is imaged onto the atoms using a 0.55 NA custom
objective. The dashed outline denotes a removable mirror which is used for
imaging the trap at low power onto a CCD camera. An EMCCD camera captures 852
nm fluorescence from the atoms, which is collected through the same objective
lens used for focusing the trap light and picked off with a long-pass
dichroic. The labeled lenses have focal lengths
$f_{1-8}=(4.5,500,250,75,200,30,150,22.8)$ mm.

For a Gaussian beam with waist parameter $w_{0}$ we have
$\epsilon_{\perp}=2/w_{0}^{2},\epsilon_{\|}=\lambda^{2}/(\pi^{2}w_{0}^{4})=1/z_{R}^{2}$.
The bright aG has similar atom distributions but with numerical corrections
close to unity. The results for Gaussian, aG, and dark aG potentials are
summarized in Table 1.

For the dark aG trap, the potential is dominated by a quartic term to lowest
order in the radial direction. Using the Virial theorem again, we obtain

$\begin{gathered}\langle\rho^{4}\rangle=\frac{2}{3}\frac{k_{B}T}{U_{0}\epsilon_{\perp}}\\\
\sigma_{\rho}=\left(\frac{2}{3}\frac{k_{B}T}{U_{0}\epsilon_{\perp}}\right)^{1/4}\end{gathered}$
(17)

where $\epsilon_{\perp}$ is the coefficient of the quartic term in the radial
expansion of the potential.

In practice, the radial and axial confinement provided by a trap potential is
found by a parametric heating experiment to deduce the vibrational frequencies
of the trapped atoms. These are well defined along directions for which the
potential is harmonic to lowest order. For a trap which closely approximates a
Gaussian potential of waist $w_{0}$, with trap depth $U_{0}$ for an atom of
mass $m$, we have

$\begin{gathered}\omega_{\rho}=\frac{2}{w_{0}}\sqrt{\frac{U_{0}}{m}}\\\
\omega_{z}=\frac{1}{hz_{R}}\sqrt{\frac{2U_{0}}{m}}\end{gathered}$ (18)

For a perfect Gaussian beam, $h=1$. For the bright aG beam, which diverges
somewhat slower in the axial direction, $h=1.307$, and for the dark aG trap
$h=0.997$. In the case of the dark aG trap, the radial profile is dominated by
a quartic term, so the radial motion of trapped atoms will obey the unforced
Duffing equation [18]. Hence, a particular vibrational frequency is not well-
defined in this case. A summary of the trap frequencies and spatial
confinement is given in Table 1.

Figure 3: Dark trap intensity profile with broadband, spatially multimode
light. (a) The focal plane of traps imaged onto a CCD, formed with a $4f$
filtering system with a magnification of 1/10, giving an array period of
$43~{}\mu$m in the imaging plane. For the $\lambda=805~{}$nm light used, (b)
the Talbot plane is located at $z=4.6$ mm, where the re-imaged traps have been
strongly suppressed. (c) and (e) show a single trap site with 808 nm multimode
light projected on the focal plane and along the propagation plane
intersecting $\rho=0$. For qualitative comparison, (d) and (f) show numerical
simulations of the trap using coherent single mode light

##  III Experiment

We demonstrate the proposed method of creating a blue-detuned dark trap array
with up to 1225 sites for trapping single Cs atoms, and compare the use of an
incoherent laser versus a coherent laser. The trap array is formed using a
commercially fabricated (by LaserOptik) custom mask consisting of a $35\times
35$ grid of partially transmitting disks of radius $a=100~{}\mu$m
($|t_{a}|^{2}=0.49$; see Appendix D.1) and spatial period
$d=430~{}\mu\textrm{m}$, positioned on a 25.4 mm diameter glass blank AR
coated for a design wavelength of 825 nm. The experimental setup, shown in
Fig. 2, is the same for trapping with both coherent and incoherent lasers
except for the lasers themselves and the optics that precede the array mask.
The array mask and $4f$ telescope is followed by an intermediate pick off for
imaging the trap intensity with a magnification of roughly $1/10$, and the
array is imaged into the science chamber to have a spatial period of 3 $\mu$m
at the atoms. We emphasize that for a given array mask, the period of the
array at the atoms and the trap depth can be tuned by changing the
magnification of the imaging system.

###  III.1 Incoherent trap

Figure 4: Single atom loading in a 1225-site array of dark traps formed with a
broadband, spatially multimode laser. See section III. (a) Single fluorescence
image, showing stochastic loading of the trap array. The spacing between trap
sites is about $3~{}\mathrm{\mu m}$. (b) Averaged fluorescence image processed
with independent component analysis. (see Appendix D.3). (c) Histograms of
photocounts from regions of interests defined for the central 49 sites in
(a),(b), showing the well-separated background (pink) and single atom (dark
red) distributions.

First, we present single atom trapping in a 2D 1225-site dark trap array with
a high power spatially multimode, broadband 808 nm laser (Aerodiode CCMI, 35
W), which is blue-detuned with respect to the Cs D-lines. Going forward, we
will simply refer to this laser as the “incoherent” laser.

The incoherent light is used in order to form the optical trap array without
incurring the formation of Talbot plane traps, as shown in Fig. 3. For an
explanation of the dominant mechanism in destroying the Talbot interference,
see Appendix C. The entire array mask was illuminated and imaged onto a CCD
following a $4f$ filtering setup. In order to have uniform trap depths across
the array, it is crucial to uniformly illuminate the mask, which we do by re-
imaging the core of a $200~{}\mu$m multimode fiber on to the mask. This is a
good approximation to illuminating the mask with a top-hat intensity profile.
An adjustable iris was used as the spatial filter in the $4f$ setup, and tuned
to a radius of about 0.5 mm to minimize the trap center intensities as viewed
on a CCD camera. To characterize the trap, we begin by stochastically loading
single Cs atoms from a MOT into the array, for which we observe up to about
50$\%$ filling of the array. The trap light is switched on by controlling the
laser current, instead of using an AOM, due to poor diffraction efficiency
with the multimode light. Fluorescence images of atoms loaded into the array
are shown in Fig. 4, with an average single atom loading rate in excess of
30$\%$ for the data shown. The loading rate observed with coherent trapping
light, discussed below, was about 50$\%$. We attribute the increase in loading
rate with coherent light to the difference in relative intensity noise (RIN)
between the two lasers (see Appendix D.2).

The axial and radial frequencies of the atoms in the trap were measured to be
about 6 kHz and 44 kHz, respectively, by parametric heating from modulating
the laser current with a sinusoidal source. For the particular mask used, we
expect a trap which diverges faster in the axial direction compared to the
expansion given in eq. (10), providing tighter axial confinement. For the
radial direction, the trap closely matches a harmonic potential, and therefore
the standard radial frequency relation (see eq. (18)) for a harmonic potential
applies (see Appendix D.1). Hence there are three free parameters in the pair
of trap frequency equations: the best-fit Gaussian waist $w_{0}$, trap depth
$U_{0}$, and divergence parameter $h$. It is not straightforward to predict
$h$ due to the unknown $M^{2}$ for the incoherent light, so we use the two
trap frequencies to solve for $h$ and $U_{0}$, given a value of $w_{0}$ found
using the known imaging magnification and a calibrated fit of the trap
intensity. For a fit waist of 1.6 $\mu$m, the trap frequencies imply
$U_{0}/k_{B}=462~{}\mu$K and $h=0.647$. The polarizability of the Cs
$6\rm{S}_{1/2}$ states is $\alpha_{0}=0.66\times 10^{-6}~{}\rm{\mu
K/(W/m^{2})}$ at 808 nm, and the estimated intensity at the atoms is
$7.06\times 10^{8}~{}\rm{W/m^{2}}$ (with about 20 W of light), giving an
expected trap depth of $U_{0}/k_{B}=466~{}\rm{\mu K}$. This agrees with the
value implied by the trap frequencies to within a few percent, and $h$ is of
the same order as the numerical prediction with coherent light.

The observed atom lifetime in the incoherent trap was about 40 ms, in
comparison to about 5 s measured with the coherent trap to be discussed next.
We attribute this difference to the RIN of each laser (see Appendix D.2).
Nevertheless, we emphasize there is nothing fundamentally prohibitive for
obtaining reasonable trap lifetimes in multimode optical traps [19, 20].
Moreover, intensity-noise limited trap lifetimes can be significantly improved
using well developed noise reduction techniques such as the method used in
[21], which uses an AOM and EOM for slow and fast noise reduction,
respectively. We note that the poor diffraction efficiency of an AOM with
multimode light is not a barrier to intensity stabilization as it was to using
an AOM as an optical switch. This is because using an AOM for intensity
stabilization requires dumping a relatively small amount of power into the
diffracted order. Furthermore, the intensity stabilization scheme in [21]
could be modified to use two EOMs instead of one AOM and one EOM, if
diffraction efficiency is a concern.

###  III.2 Coherent trap

The same trap characterization experiments were repeated using a coherent 825
nm laser (Moglabs MSA003 tapered amplifier), where the only change to the
experimental setup was the optics for collimating the trap light before the
array mask. The mask was illuminated using a Gaussian beam which was
collimated after being spatially filtered by a single mode fiber. Despite the
Gaussian illumination of the mask, which leads to a varying trap depth across
the array, we still observe traps which go completely or near completely dark
across the array, indicating that uniform mask illumination is not strictly
required.

Again, we characterize the confinement by measuring the trap frequencies and
trap lifetime. The trap depth for different sites varies according to the
Gaussian intensity envelope across the array. We will therefore restrict our
analysis to values near the center of the array, where the traps are deepest.
The peak intensity at the atoms is given approximately by $I=2P/\pi w_{\rm
env}^{2}$, where $P=260$ mW is the laser power and $w_{\rm
env}=12~{}\mathrm{\mu m}$ is the Gaussian envelope waist at the atoms. This
yields about 20 to 25 sites which are deep enough for trapping. To
parametrically heat the atoms, the trap light intensity was modulated by
varying the RF power to an AOM placed before the single mode fiber delivering
light to the $4f$ filtering setup. We measure radial and axial frequencies of
about 52.5 kHz and 7.2 kHz, respectively. The rate of axial divergence, which
is faster than that of a Gaussian beam, has a divergence parameter $h=0.65$
predicted by a Fresnel diffraction simulation for the parameters of the mask
used (see ). Assuming this value of $h$, the trap frequencies imply a trap
depth of $1.4$ mK and waist $w_{0}=1.81~{}\mu$m. This waist is consistent with
the value of $1.89~{}\mu$m deduced from fitting the trap in the intermediate
imaging plane to within a few percent, and the trap depth is within our
uncertainty in measuring the intensity. Lastly, the trap lifetime was found to
be nearly 5 s, measured in the same site for which we report the trap
frequencies.

##  IV Conclusion

We have demonstrated a simple technique for creating optical trap arrays using
only passive optical components. The design lends itself to being scalable, as
a larger trap array can be created with a larger mask grid and more optical
power. This is an important point for scaling up neutral atom qubit arrays,
for which the limiting factors are optical power and the performance of the
trap imaging system[2]. As the design is based on only passive components, it
is free from noise associated with active spatial light modulators such as
DMDs.

The design presented is versatile, lending itself to several compelling
variations. Firstly, the same working principle can be used with a different
mask to simultaneously create bright and dark arrays for trapping two-species.
This can be done using a single trapping wavelength, without requiring any
additional experimental footprint compared to one-species traps. Secondly,
alternative Fourier filters can be used to create traps which provide
significantly higher localization of trapped atoms (see Appendix B).

We have also demonstrated the use of a spectrally and spatially multimode trap
for mitigating the Talbot effect, which leads to unwanted out-of-focus traps.
However, the secondary arrays of traps formed with coherent light allows for
creating a three-dimensional trap array, which may be advantageous for multi-
dimensional architectures[22, 23].

## Acknowledgments

This material is based upon work supported by the U.S. Department of Energy
Office of Science National Quantum Information Science Research Centers as
well as support from NSF Award 2016136 for the QLCI center Hybrid Quantum
Architectures and Networks, NSF award 1806548, and U.S. Department of Energy,
Office of Science, Office of High Energy Physics, under Award No. DE-
SC0019465.

## References

  * Kaufman and Ni [2021] A. M. Kaufman and K.-K. Ni, Quantum science with optical tweezer arrays of ultracold atoms and molecules, Nat. Phys. 17, 1324 (2021).
  * Morgado and Whitlock [2021] M. Morgado and S. Whitlock, Quantum simulation and computing with Rydberg-interacting qubits, AVS Qu. Sci. 3, 021101 (2021).
  * Kim  _et al._ [2019] D. Kim, A. Keesling, A. Omran, H. Levine, H. Bernien, M. Greiner, M. D. Lukin, and D. R. Englund, Large-scale uniform optical focus array generation with a phase spatial light modulator, Opt. Lett. 44, 3178 (2019).
  * Graham  _et al._ [2022] T. M. Graham, Y. Song, J. Scott, C. Poole, L. Phuttitarn, K. Jooya, P. Eichler, X. Jiang, A. Marra, B. Grinkemeyer, M. Kwon, M. Ebert, J. Cherek, M. T. Lichtman, M. Gillette, J. Gilbert, D. Bowman, T. Ballance, C. Campbell, E. D. Dahl, O. Crawford, N. S. Blunt, B. Rogers, T. Noel, and M. Saffman, Multi-qubit entanglement and algorithms on a neutral-atom quantum computer, Nature 604, 457 (2022).
  * Wang  _et al._ [2020a] Y. Wang, S. Shevate, T. M. Wintermantel, M. Morgado, G. Lochead, and S. Whitlock, Preparation of hundreds of microscopic atomic ensembles in optical tweezer arrays, npj Qu. Inf. 6, 54 (2020a).
  * Stuart and Kuhn [2018] D. Stuart and A. Kuhn, Single-atom trapping and transport in DMD-controlled optical tweezers, New J. Phys. 20, 023013 (2018).
  * Singh  _et al._ [2022] K. Singh, S. Anand, A. Pocklington, J. T. Kemp, and H. Bernien, Dual-element, two-dimensional atom array with continuous-mode operation, Phys. Rev. X 12, 011040 (2022).
  * Scholl  _et al._ [2021] P. Scholl, M. Schuler, H. J. Williams, A. A. Eberharter, D. Barredo, K.-N. Schymik, V. Lienhard, L.-P. Henry, T. C. Lang, T. Lahaye, A. M. Läuchli, and A. Browaeys, Quantum simulation of 2D antiferromagnets with hundreds of Rydberg atoms, Nature 595, 233 (2021).
  * Ebadi  _et al._ [2021] S. Ebadi, T. T. Wang, H. Levine, A. Keesling, G. Semeghini, A. Omran, D. Bluvstein, R. Samajdar, H. Pichler, W. W. Ho, S. Choi, S. Sachdev, M. Greiner, V. Vuletić, and M. D. Lukin, Quantum phases of matter on a 256-atom programmable quantum simulator, Nature 595, 227 (2021).
  * Ohl de Mello  _et al._ [2019] D. Ohl de Mello, D. Schäffner, J. Werkmann, T. Preuschoff, L. Kohfahl, M. Schlosser, and G. Birkl, Defect-free assembly of 2D clusters of more than 100 single-atom quantum systems, Phys. Rev. Lett. 122, 203601 (2019).
  * Pochernyaev [1995] V. N. Pochernyaev, Integrals of products of Bessel functions for applied electrodynamic problems, Ukrain. Math. J. 47, 658 (1995).
  * Béguin  _et al._ [2020] J.-B. Béguin, J. Laurat, X. Luan, A. Burgers, Z. Qin, and H. Kimble, Reduced volume and reflection for bright optical tweezers with radial Laguerre-Gauss beams, PNAS 117, 26109 (2020).
  * Zhang  _et al._ [2011] S. Zhang, F. Robicheaux, and M. Saffman, Magic-wavelength optical traps for Rydberg atoms, Phys. Rev. A 84, 043408 (2011).
  * Wineland and Itano [1979] D. J. Wineland and W. M. Itano, Laser cooling of atoms, Phys. Rev. A 20, 1521 (1979).
  * Piotrowicz  _et al._ [2013] M. J. Piotrowicz, M. Lichtman, K. Maller, G. Li, S. Zhang, L. Isenhower, and M. Saffman, Two-dimensional lattice of blue-detuned atom traps using a projected Gaussian beam array, Phys. Rev. A 88, 013420 (2013).
  * [16] M. Saffman and M. T. Lichtman, System and method for optical confinement of atomic particles, U. S. Patent 9,355,750 B2, (2016).
  * Beterov and Saffman [2015] I. I. Beterov and M. Saffman, Rydberg blockade, Förster resonances, and quantum state measurements with different atomic species, Phys. Rev. A 92, 042710 (2015).
  * Kovacic and Brennan [2011] I. Kovacic and M. J. Brennan,  _The Duffing Equation: Nonlinear Oscillators and their Behaviour_ (Wiley, 2011).
  * Hung  _et al._ [2015] W. Hung, P. Huang, F.-C. Wu, M. Bruvelis, H.-Y. Xiao, A. Ekers, and I. A. Yu, Storage time of cold Rb atoms in an optical dipole trap formed by a multimode fiber laser, J. Opt. Soc. Am. B 32, B32 (2015).
  * Povilus  _et al._ [2005] A. P. Povilus, S. E. Olson, R. R. Mhaskar, B.-K. Teo, J. R. Guest, and G. Raithel, Time averaging of multimode optical fiber output for a magneto-optical trap, J. Opt. Soc. Am. B 22, 311 (2005).
  * Wang  _et al._ [2020b] Y. Wang, K. Wang, E. F. Fenton, Y.-W. Lin, K.-K. Ni, and J. D. Hood, Reduction of laser intensity noise over 1 MHz band for single atom trapping, Opt. Expr. 28, 31209 (2020b).
  * Wang  _et al._ [2016] Y. Wang, A. Kumar, T.-Y. Wu, and D. S. Weiss, Single-qubit gates based on targeted phase shifts in a 3D neutral atom array, Science 352, 1562 (2016).
  * Barredo  _et al._ [2018] D. Barredo, V. Lienhard, S. de Léséleuc, T. Lahaye, and A. Browaeys, Synthetic three-dimensional atomic structures assembled atom by atom, Nature 561, 79 (2018).
  * Graham  _et al._ [2019] T. Graham, M. Kwon, B. Grinkemeyer, A. Marra, X. Jiang, M. Lichtman, Y. Sun, M. Ebert, and M. Saffman, Rydberg mediated entanglement in a two-dimensional neutral atom qubit array, Phys. Rev. Lett. 123, 230501 (2019).
  * Kelly  _et al._ [2014] J. Kelly, R. Barends, B. Campbell, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, A. G. Fowler, I.-C. Hoi, E. Jeffrey, A. Megrant, J. Mutus, C. Neill, P. J. J. O’Malley, C. Quintana, P. Roushan, D. Sank, A. Vainsencher, J. Wenner, T. C. White, A. N. Cleland, and J. M. Martinis, Optimal quantum control using randomized benchmarking, Phys. Rev. Lett. 112, 240504 (2014).
  * Gehm  _et al._ [1998] M. E. Gehm, K. M. O’Hara, T. A. Savard, and J. E. Thomas, Dynamics of noise-induced heating in atom traps, Phys. Rev. A 58, 3914 (1998).

##  Appendix A Robustness of $4f$ filtered traps

A natural question to pose is to what extent the $4f$ filtering approach to
generating traps is sensitive to parameters, such as the mask transmission
amplitudes, Fourier filter radius, and the intensity profile used to
illuminate the mask. Here we address this for the case of generating dark
traps. The metric we find most useful is simply to quantify the relative
intensity at the centers of the traps, that is, $I_{2}(0,0)/I_{0}$ (eq. (9)).
The derivation of the dark trap found the condition for completely dark traps
given zero relative phase between the mask aperture and background
transmission amplitudes, $t_{a},t_{b}$, and a choice of filter radius $b$
corresponding to blocking the Airy disk beyond the first minima.

Figure 5: Numerical analysis of dark aG trap profile dependence on relative
mask phase $\phi_{ab}$ and Fourier filter (iris) radius. The iris radii here
are given as dimensionless by dividing by the value used in the derivation in
the main text, $b=x^{(1)}_{1}f_{1}/ak$. (a) Trap profile data (purple points)
from Fig. 3a compared to two Fresnel diffraction calculations: one with
parameters which give a similar profile (purple dashes), and one with
parameters corresponding to the expected trap given the specified parameters
of the mask used (red line). Both parameter sets use
$f_{1}=500$mm,$f_{2}=50$mm, $\lambda=805$nm, with the former using
($\phi_{ab}$, iris radius) = ($160^{\circ}$,0.4), and ($0^{\circ}$,1) for the
latter. (b) and (c) show the dark trap center intensity (log scale) versus
$\phi_{ab}$ and iris radius. The choices of $\phi_{ab}$ and iris radius used
to generate the numerical curves in (a) are marked with rings of the same
color in (c).

However, the trap can be made near completely dark for other choices of these
parameters. Fig. 5 shows the trap center intensity for two values of $t_{a}$
(and $t_{b}=1$), as a colormap versus the relative phase $\phi_{ab}$ between
$t_{b},t_{a}$ and the Fourier filter or iris radius cast in dimensionless
units. For $t_{a}=0.287$, as derived as optimal above, we see the trap remains
dark to within about $10\%$ for up to around 20 degrees of relative mask
phase, indicating the robustness of the design with respect to deviance in
parameters from manufacturing of a real mask.

##  Appendix B Tighter traps with alternative Fourier plane masks

It is possible to create tighter trap profiles than those presented in the
main text, by replacing the simple Fourier plane iris with more complicated
amplitude or phase masks. For example, a higher efficiency (eq. (5)) bright
trap can be created by using a modified Fourier plane amplitude mask which
transmits certain higher spatial frequency bands. This amounts to adding
spatial notch filters, i.e. transmitting rings, to a low-pass filter as used
in the main text. It can be shown that the transparent rings should have inner
and outer radii equal to $f_{1}x_{2n}^{(1)}/(ak)$, $f_{1}x_{2n+1}^{(1)}/(ak)$
respectively, for the $n^{th}$ ring from the center, for $n>1$. The central
aperture has radius $f_{1}x_{1}^{(1)}/(ak)$. This type of filter, which we
refer to as a Fresnel zone filter, is shown with only one ring in Fig. 6
alongside the resulting trap profiles compared to those of a standard aG beam.
It is apparent from the figure that the resulting traps have much stronger
confinement than is obtained with the simple low pass filter. Compared to the
bright aG trap, the trap generated with the zone filter has roughly 1.9 times
higher efficiency (corresponding directly to the trap depth), with about 2.2
and 10 times tighter confinement in $\rho$ and $z$, respectively. The zone
filter does introduce weak secondary traps away from the origin. Atom trapping
in the secondary traps can be avoided, either by slowly increasing the trap
power during the loading phase, or by using atom rearrangement techniques to
place atoms in the central trap.

Figure 6: Comparison between an aG beam produced with a low-pass Fourier
filter (see main text) and a modified version using a ”Fresnel zone” Fourier
filter. The horizontal axes are scaled to the best fit Gaussian waist $w_{0}$
and corresponding Rayleigh range $z_{R}=\pi w_{0}^{2}/\lambda$ for the aG
beam. The two Fourier filter variants are shown in the inset, and the radii of
the transmitting rings and central aperture are given in the text.

##  Appendix C Talbot Trap Mitigation

In cold atom experiments using periodic optical trap arrays, it is a known
problem that secondary traps, which form due to the Talbot effect, lead to
out-of-focus trapped atoms. This contributes additional background in
fluorescence measurements used for atom state detection and atom rearrangement
[24]. The Talbot effect is a well-known phenomenon in optics, in which a field
which is spatially periodic in the transverse plane will be reimaged after
propagating a distance equal to

$z_{\text{Talbot}}=\frac{2d^{2}}{\lambda}$

where $d$ is the transverse spatial period of the field and $\lambda$ is the
wavelength of the field. Numerical simulations of the first Talbot planes for
dark and bright trap arrays are shown in Fig. 7 We propose a solution using a
spatially and spectrally incoherent laser field.

Figure 7: Comparison of simulated Talbot plane trap formation for a 10 by 10
dark aG array formed with (a) spatially coherent monochromatic light and (b)
spectrally and spatially incoherent field. For the incoherent light, 21
frequency components spanning $\Delta\lambda_{\rm FWHM}=3$ nm, each with 200
Hermite-Gaussian modes with random phases. The insets show the the focal plane
intensity. The plot axes are scaled to the best fit Gaussian waist,
$w_{0}=0.943a(f_{2}/f_{1})$. (c) Line profile comparison of a row of traps
from (a) and (b), showing the washed out Talbot interference for the multimode
light. For both simulations, $\lambda_{0}=825$ nm, $d=430~{}\mu$m, and
$a=100~{}\mu$m, and a magnification of 1/100.

The Talbot effect can be mitigated by use of a spatially multimode laser,
which has a limited spatial coherence. In what follows we will limit the
numerical analysis to the case of a dark trap array, although much of the
discussion is equally applicable to bright traps. In addition to being
spatially multimode, it is desirable to have many frequency components as
well. This ensures that the bright region of the trap does not exhibit a
speckle pattern, which could create additional unwanted traps. This section
will outline results of numerical simulation. The experimental confirmation of
these predictions shown in Sec. III of the main text.

The models presented here use Fresnel diffraction theory, which is readily
computed using fast Fourier transform (FFT) algorithms that are available in
modern programming languages [25]. This modeling can be done efficiently on a
typical laptop. For computational efficiency, the results presented below are
for 10-by-10 trap arrays. All of the Talbot plane intensity plots shown are
normalized to the respective peak focal plane intensity, to provide a clear
sense of the relative trap depth. For the simulations discussed, the laser
wavelength is $\lambda=825$ nm, mask grid period $d=430~{}\mu$m, mask spot
radius $a=100~{}\mu$m, aperture transmission $t_{a}=0.287$. However, the
results are presented in a way that is independent of the choice of parameters
such as focal lengths and wavelength.

Let us first consider an array of optical traps formed by a laser which has
many frequency components, but is spatially coherent. Far-off resonance
optical traps do not require narrow-linewidth lasers, and hence the use of a
free-running, broadband laser is feasible. Naively, we may assume that if the
coherence length of the laser is less than the Talbot length of the trap
array, the Talbot traps will be suppressed. To quantify how short the
coherence length must be in order for the Talbot traps to be washed out, we
need to consider 1) the axial displacement of the Talbot plane for a given
$\Delta\lambda$ from the central trap wavelength $\lambda_{0}$, and 2) the
axial depth of the Talbot traps. The depth of the Talbot plane is $\delta
Z_{\textrm{Talbot}}\sim\pi w_{0}^{2}/\lambda$ where $w_{0}=0.947af_{2}/f_{1}$
is the waist of the trap (for the case of the bright array), and the amount
that the Talbot plane is displaced for a change in $\lambda$ is
$2\Delta\lambda d^{2}/\lambda^{2}$. Combining these, we find that in order to
displace the Talbot plane by half of its axial depth, we require a laser with
a spectral full-width of

$\Delta\lambda_{1/2}=\frac{\pi\lambda}{2}\frac{a^{2}}{d^{2}}\frac{f_{2}^{2}}{f_{1}^{2}}$
(19)

For $a=100~{}\mu$m and a magnification of $1/100$, a laser with a FWHM of more
than 10 nm is required to sufficiently wash out the Talbot plane. Typically,
even lower quality laser diodes have linewidths of at most a few nm,
insufficient for mitigating Talbot trap formation for the trap parameters
considered. However, as we will show, spectral incoherence still plays an
important role in the demonstrated solution to the Talbot problem.

We find that a practical and cost-effective approach to mitigating Talbot
traps is using a laser which is both spectrally and spatially incoherent,
which are readily available at high power. By using a spatially multimode
field, there is no longer spatial coherence which is required for forming the
Talbot planes. A monochromatic but spatially incoherent field, as can be made
by passing a laser with a single spatial mode through a multimode fiber, has a
speckled intensity and hence is not a good solution for creating trap arrays.
A spectrally and spatially multimode field will, however, not be speckled.
This is explained by thinking of each spectral component as having its own
associated speckle pattern. These speckle patterns add incoherently, i.e. the
intensities rather than the fields are summed, resulting in a more uniform
intensity pattern.

We model spatially incoherent fields by summing Hermite-Gaussian fields
$A_{i,j}$ from $A_{0,0}$ to some highest-order $A_{m,n}$, with each spatial
mode being given a random phase pulled from a flat distribution. This process
is done for each spectral component of the field and scaled by
$\sqrt{L(\nu,\nu_{0})}$ where $L$ is the Lorentzian function describing the
spectral width of the laser. Each speckle field is then propagated through the
$4f$ array generator and the intensities at the output are summed, yielding
the output shown in Fig. 7b.

##  Appendix D Experimental details

###  D.1 Array mask and observed trap profiles

The experimental demonstration of the proposed trap design used a commercially
fabricated array mask consisting of partially transmitting disks (what we have
previously been calling “apertures”) set on an AR-coated 1” diameter glass
blank. The requested transmission of the disks was $|t_{a}|^{2}=0.49\pm 0.04$,
with a relative phase of $0\pm 10$ deg. between the disks and AR coated
background, designed for $\lambda=825$ nm. The disks have radius
$a=100~{}\mu$m and arranged in a 2D square grid with spatial period
$d=430~{}\mu$m. The expected trap profile for these mask parameters does
yields traps which are only about 50$\%$ dark (Fig. 5a). However, given the
observed nearly dark traps and numerical analysis, we infer that the relative
phase imparted on the light between the fully and partially transmitting
regions must be outside of the specified tolerance in order to explain the
observed trap profiles.

Figure 8: A row of adjacent trap site profiles from the data shown in Fig. 2,
where each site has been fit to a form $a\rho^{\alpha}+b$. The data was
clipped above the $1/e$ intensity to ensure fitting to the lower order
portions of the traps. It is clear that the experimentally observed radial
profiles are nearly quadratic, rather than the quartic profiles expected for
$t_{a}=0.287t_{b}$ with zero relative mask phase.

Because a direct phase measurement of the array mask is difficult, we present
numerical analysis to explain the observed trap profile. These results are
summarized in Fig. 5. The observed traps can be made dark to within $10\%$ of
the peak intensity by adjusting the iris radius. This constrains the possible
values of $\phi_{ab}$ and iris radius that are consistent with the trap we
observe. For example, a Fresnel diffraction calculation for $t_{a}=0.7$, iris
radius $b=0.4x^{(1)}_{1}f_{1}/ak$ and $\phi=160^{\circ}$, gives a result that
agrees well the observed trap profiles (Fig. 5a, purple dashes). This choice
of parameters is marked with a purple ring in Fig. 5b.

Moreover, the axial divergence rate of the trap is in good agreement with the
measured trap frequencies. It can be shown that the quadratic term of the
axial expansion for $\phi_{ab}=160^{\circ}$ and $b=0.4x^{(1)}_{1}f_{1}/ak$ is
equal to $2.356(z/z_{R})^{2}$, giving a divergence parameter
$h=1/\sqrt{2.356}=0.65$. This is an additional advantage conferred by the mask
parameters, as the axial confinement is $\sim 30\%$ tighter compared to the
expansion rate using $t_{a}=0.287$ and $\phi_{ab}=0$. As stated in the main
text, the measured trap frequencies predict a trap waist and depth consistent
with estimates of this value of $h$ is assumed in eq. (18).

Lastly, the measurement of well-defined vibrational frequencies discussed in
the main text is a result of the quadratic profile of the observed traps. This
is shown with power fits to a row of adjacent sites in Fig. 8. It can be shown
that the quadratic coefficient in the radial expansion of the trap profile,
for $t_{a}=0.7$, is only finite and positive for certain values of the
relative mask phase $\phi_{ab}$ and iris radius, including
$\phi_{ab}=160^{\circ}$ and $b=0.4x^{(1)}_{1}f_{1}/ak$.

###  D.2 Atom lifetime in incoherent trap

We attribute the observed characteristic lifetime of atoms in the incoherent
trap, about 40 ms, to the RIN measured on the laser, shown in Fig. 9. While
the level of the RIN near 68 kHz (twice the measured observed radial
resonance) implies a lifetime of over 8 seconds [26], there is a lower
frequency bump nearby and several high amplitude spikes. Because the atom is
heated by these other components as well, we take this noise to be the
explanation of the observed poor lifetimes.

Figure 9: RIN spectrum for the incoherent 808 nm laser and coherent 825 nm
lasers used for atom trapping. The atom lifetime in the incoherent trap was
measured to be 40 ms, in contrast to a lifetime of at least 5 s measured with
the coherent trap. The dashed blue line corresponds to the twice the measured
radial vibration frequency, where the 808 nm RIN level implies a lifetime in
excess of 8 s. However, the many large frequency spikes can induce off-
resonant heating.

The RIN for a coherent laser used for trapping is shown for comparison, for
which we measured a lifetime around 5 s. Note that the seed laser for the
coherent tapered amplifier used for experiments described in the main text
(for which a 7 s trap lifetime was observed) died before RIN data could be
measured.

###  D.3 Fluorescence imaging

The fluorescence images of trapped atoms were captured on a Hamamatsu C9100-13
EMCCD with 100 ms exposure time. The imaging light was 852 nm, red detuned
from the D2 line cooling transition $F=4\leftrightarrow F^{\prime}=5$ by about
9 times the natural linewidth, with an intensity around three times the
saturation intensity. The single shot image of trapped atoms in Fig. 2a is
divided by the average background for the stack of 300 shots taken for that
data to account for an uneven intensity pattern on the shots due to a gain
variation on the EMCCD sensor itself. The large image was processed with
independent component analysis, which has the effect of de-blurring the
trapped atoms. However, due to the size of the image (512 by 512 pixels), this
process was only effective when the image was broken into smaller chunks.
Ultimately, 25 sub-regions in the image stack were processed, and the the
summed projected images were stitched back together. The result exhibited a
uniform background in each sub-image, with a slight variation between the
background level in adjacent sub-regions. Hence, for visual purposes only, the
resulting image was plotted with the pixels valued less than 20$\%$ of the
maximum intensity clipped.


TU Dortmund<EMAIL_ADDRESS>TU Eindhoven, The
<EMAIL_ADDRESS>Mart Hagedoorn and Irina Kostitsyna [100]Theory
of computation Design and analysis of algorithms

# The Shortest Path with Increasing Chords in a Simple Polygon

Mart Hagedoorn  Irina Kostitsyna

###### Abstract

We study the problem of finding the shortest path with _increasing chords_ in
a simple polygon. A path has increasing chords if and only if for any points
$a,b,c$, and $d$ that lie on the path in that order, $|ad|\geq|bc|$. In this
paper we show that the shortest path with increasing chords is unique and
present an algorithm to construct it.

###### keywords:

self-approaching paths, paths with increasing chords

##  1 Introduction

Figure 1: The shortest $s$-$t$ path with increasing chords inside simple
polygon $P$.

An $s$-$t$ path $\sigma$ has _increasing chords_ if and only if $\sigma$ is a
directed path from some point $s$ to $t$ and for any points $a,b,c$, and $d$
that appear in that order on $\sigma$, the Euclidean distance between $a$ and
$d$ is greater or equal to the Euclidean distance between $b$ and $c$ [6].
Figure 1 shows an example of a shortest $s$-$t$ path with increasing chords in
simple polygon $P$. Furthermore, a path has increasing chords if and only if
the path is _self-approaching_ in both directions. A path is self-approaching
if, when traversing the path the Euclidean distance to any point on the
remainder of the path is not increasing.

Paths with increasing chords are closely related to beacon and greedy routing
applications. Path finding with beacon and greedy routing often results in
paths that are directed curves such that the distance to the destination is
never increasing [2, 1, 4]. Paths with this property are called _radially
monotone paths_. If a path has increasing chords, then every subpath of that
path is radially monotone in both directions.

Furthermore, self-approaching paths and paths with increasing chords have the
property that the length of the path is bounded in comparison with the
Euclidean distance between the start and destination of the path. This
bounding factor of paths with increasing chords is only $2\pi/3$, whereas the
bounding factor of self-approaching paths is approximately $5.3331$ [7, 5].

The results of this paper are further discussed in the master’s thesis of
Hagedoorn.

##  2 Preliminaries

An $s$-$t$ path $\zeta$ is a directed curve that starts in point $s$ and ends
in point $t$. Moreover, path $\zeta$ must lie entirely inside of polygon $P$,
i.e. $\zeta\subseteq P$. We define $\zeta(p,q)$ to be the subpath of $\zeta$
that lies between points $p$ and $q$. Paths in a Euclidean space can make
smooth turns and sharp turns. In order to differentiate between these types of
turns, we use the standard notation of a _bend point_ (Fig. 2). A _bend point_
$b$ of a piecewise smooth curve $\zeta$ is a point where the first derivative
of $\zeta$ is discontinuous.

Figure 2: The normal $h_{p}$ of $p$, where $p$ is a bend point.

Furthermore, we define a _normal_ $h_{p}$ to path $\zeta$ at point $p$ to be
the line through $p\in\zeta$ such that $h_{p}$ is perpendicular to the tangent
of $\zeta$ in $p$. If $p$ is a bend point, then we use the normal definition
as proposed by Icking et al. [5]. This definition states that the normal to
$\zeta$ at $p$ is the set of lines that are included in the double wedge
between the perpendicular lines to the tangents of the smooth pieces meeting
at $p$ (Fig. 2).

Figure 3: The shortest self-approaching $s$-$t$ path inside simple polygon
$P$.

###  2.1 Self-approaching paths

Self-approaching paths were first described by Icking et al. [5]. A path $\pi$
is self-approaching if and only if for any points $a,b$, and $c$ that appear
on $\pi$ in that order, the Euclidean distance between $a$ and $c$ is greater
or equal to the Euclidean distance between $b$ and $c$ (Fig. 3). Furthermore,
Icking et al. [5] showed the following _normal property_ of self-approaching
paths.

######  Lemma 1 ([5]).

An $s$-$t$ path $\pi$ is self-approaching if and only if the normal to $\pi$
at any point $p\in\pi$ does not intersect the subpath $\pi(p,t)$.

Figure 4: Dead region $\mathcal{D}_{t}$ (red) for some point $t$ in simple
polygon $P$.

Bose et al. [3] proposed an algorithm for finding the shortest _self-
approaching_ $s$-$t$ path in a simple polygon $P$ (Fig. 3). Their algorithm
uses the notion of _dead regions_. A dead region $\mathcal{D}_{t}$ for point
$t$ is a set of points such that for any point $s\in\mathcal{D}_{t}$, no self-
approaching $s$-$t$ path exists (Fig. 4). They proved that the shortest self-
approaching $s$-$t$ path $\pi$ is the $s$-$t$ geodesic in
$P\setminus\mathcal{D}_{t}$, i.e. the set difference of the polygon and the
dead region for point $t$. Therefore, the shortest self-approaching $s$-$t$
path consists of straight line segments and segments that are boundaries of
$\mathcal{D}_{t}$. Moreover, they showed that if $v$ is a point on $\pi$ and
$v$ lies on a boundary of $\mathcal{D}_{t}$, then the normal $h_{v}$ to $\pi$
at $v$ must _touch_ the subpath $\pi(v,t)$. A line $\ell$ touches a curve
$\gamma$ if there exists some point $p$ such that $\ell\cap\gamma=\\{p\\}$ and
for the normal $h_{p}$ to $\gamma$ at point $p$, $\ell\in h_{p}$ or
$\ell=h_{p}$ when $p$ is a bend point or not, respectively.

The equations that define boundaries of $\mathcal{D}_{t}$ are transcendental
equations and likely cannot be solved or evaluated analytically [3].
Therefore, the shortest self-approaching path can only be found if we assume
these equations can be solved or that an approximation of the path will be
calculated.

###  2.2 Paths with increasing chords

As mentioned before, a path $\sigma$ has increasing chords if and only if
$\sigma$ is self-approaching in both directions. Furthermore, for paths with
increasing chords we can again define the normal property:

######  Lemma 2.

An $s$-$t$ path $\sigma$ has increasing chords if and only if the normal to
$\sigma$ at any point $p\in\sigma$ does not intersect the subpaths
$\sigma(s,p)$ and $\sigma(p,t)$.

###### Proof.

A path $\sigma$ with increasing chords is self-approaching from $s$ to $t$ and
from $t$ to $s$. Therefore, at any point $p\in\sigma$ the normal properties of
the self-approaching $s$-$t$ and $t$-$s$ paths state that $\sigma(s,p)$ and
$\sigma(p,t)$ cannot cross the normal to $\sigma$ at point $p$. ∎

Figure 5: Example figure showing the normal $h_{p}$ at point $p$ and the
corresponding half planes $h_{p}^{-}$ and $h_{p}^{+}$.

This property above can be reformulated in terms of the _negative_ and
_positive half-plane_. Using the definition from Bose et al. [3], the positive
half-plane $h_{p}^{+}$ of path $\zeta$ at point $p$ is the closed half-plane
that is defined by normal $h_{p}$ to $\zeta$ and contains at point $p$ which
is congruent to the direction of $\zeta$ at $p$. Analogously, the negative
half-plane $h_{p}^{-}$ is congruent with the opposite direction of $\zeta$ at
$p$ (Fig. 5).

######  Corollary 3.

An $s$-$t$ path $\sigma$ has increasing chords if and only if, for any line
$h$ normal to $\sigma$ at point $p\in\sigma$, the subpath $\sigma(s,p)$ lies
completely in the negative half-plane $h_{p}^{-}$ and the subpath
$\sigma(p,t)$ lies completely in the positive half-plane $h_{p}^{+}$.

##  3 Shortest Path with Increasing Chords

In this section we first show that a shortest $s$-$t$ path with increasing
chords in a simple polygon is unique. Therefore, we only need to search for
one shortest $s$-$t$ path with increasing chords. The following two proofs are
extensions from the analogous propositions about self-approaching paths given
by Bose et al. [3].

Figure 6: Geodesic $\gamma$ (purple) that lies between paths $\sigma_{1}$
(blue) and $\sigma_{2}$ (red) with increasing chords.

######  Lemma 4.

A geodesic path $\gamma$ between two distinct paths with increasing chords
$\sigma_{1}$ and $\sigma_{2}$ also has increasing chords (Fig. 6).

###### Proof.

We will use the fact that the geodesic must lie in both convex hulls of both
paths, i.e. $\gamma\subseteq\textit{CH}(\sigma_{1})$ and
$\gamma\subseteq\textit{CH}(\sigma_{2})$. Furthermore, any point $p\in\gamma$
either lies on one of the paths $\sigma_{1}$ or $\sigma_{2}$ or on a straight
line that is bitangent to $\sigma_{1}$, $\sigma_{2}$ or both $\sigma_{1}$ and
$\sigma_{2}$.

First, we consider the case that $p$ is not a bend point but lies on a smooth
section of $\sigma_{1}$ or $\sigma_{2}$. Let, w.l.o.g., $p\in\sigma_{1}$. The
positive half-plane $h_{p}^{+}$ of the normal to $\sigma_{1}$ at $p$ contains
subpath $\sigma_{1}(p,t)$ and the negative half-plane $h_{p}^{-}$ of the
normal at $p$ contains subpath $\sigma_{1}(s,p)$. Therefore, $h_{p}^{+}$ also
contains the convex hull of $\sigma_{1}(p,t)$ and $h_{p}^{-}$ contains the
convex hull of $\sigma_{1}(s,p)$. Hence, $h_{p}^{+}$ contains the subpath
$\gamma(p,t)$ and $h_{p}^{-}$ contains the subpath $\gamma(s,p)$ of the
geodesic.

Now let $p$ be a bend point lying on $\sigma_{1}$. Subpath $\sigma_{1}(p,t)$
must be fully contained in the two positive half-planes, which are defined by
the normals of the smooth pieces of $\sigma_{1}$ meeting at $p$. Analogously
$\sigma_{1}(s,p)$ is fully contained in the two negative half-planes. The two
normals of the geodesic path at this point must also lie in between the two
normals to the boundary path. Thus, the intersection of the two positive half-
planes of the normals to the geodesic contains the convex hull of the subpath
$\sigma_{1}(p,t)$, and, therefore, the rest of the geodesic path
$\gamma(p,t)$. Analogously, the intersection of the two negative half-planes
of the normals to the geodesic contains the convex hull of the subpath
$\sigma_{1}(s,p)$, and, therefore, the geodesic subpath $\gamma(s,p)$.

Finally, let $p$ lie on a segment of $\gamma$ that is bitangent to
$\sigma_{1}$, $\sigma_{2}$ or both $\sigma_{1}$ and $\sigma_{2}$. Let us
consider one of the end-points $p^{*}$ of this bitangent. Assume, that
$p^{*}\in\gamma(p,t)$. The normal to $\gamma$ at $p$ is parallel to the normal
to $\gamma$ at $p^{*}$. By one of the cases considered above, the positive
half-plane at $p^{*}$ will contain $\gamma(p^{*},t)$, and, therefore, the
positive half-plane of the normal to $\gamma$ at $p$ will also contain the
subpath $\gamma(p,t)$. If $p^{*}\in\gamma(s,p)$, then we can follow analogues
steps to show that $\gamma(s,p)$ lies in the negative half-plane of $p$.

Thus, $\gamma$ has increasing chords. ∎

Using Lemma 4 we can prove the following Theorem.

######  Theorem 5.

A shortest $s$-$t$ path with increasing chords in a simple polygon is unique.

###### Proof.

Assume there exist two distinct shortest $s$-$t$ paths with increasing chords
$\sigma_{1}$ and $\sigma_{2}$ in a polygon $P$. Then, by Lemma 4, there exists
a shorter path that is a geodesic path enclosed between $\sigma_{1}$ and
$\sigma_{2}$. ∎

In the next theorem we show that if we subtract the union of dead regions
$\mathcal{D}_{t}$ and $\mathcal{D}_{s}$ from a simple polygon $P$, then the
shortest $s$-$t$ path in this space is also the shortest $s$-$t$ path with
increasing chords. This theorem is proven by contradiction. In more detail, we
show that if there is a point where the normal property is violated, then no
self-approaching path can exist.

######  Theorem 6.

Let $s$ and $t$ be two points in a simple polygon $P$. The shortest path
between $s$ and $t$ in $P\setminus(\mathcal{D}_{t}\cup\mathcal{D}_{s})$ is the
shortest $s$-$t$ path with increasing chords in simple polygon $P$.

###### Proof.

Figure 7: Shortest path $\sigma$ (purple) where the normal property does not
hold in $p^{\prime}$, normal $h_{p}$ touches point $q$ that lies on subpath
$\rho$ (blue) of $\sigma$.

Figure 8: Shortest path $\sigma$ (purple) where the normal property does not
hold in $p^{\prime}$, normal $h^{\prime}_{b}$ touches point $q$ that lies on
subpath $\rho$ (blue) of $\sigma$.

Assume that $\sigma$ does not have increasing chords, hence the normal
property is violated at some point of $\sigma$. Let point $p\in\sigma$ be the
last point on $\sigma$ for which the normal property holds. Point $p$ is not
guaranteed to exist. However, if $p$ exists, then there also exists point
$p^{\prime}\in\sigma(p,t)$ such that $p^{\prime}$ lies in the
$\epsilon$-neighborhood of $p$ for arbitrary small $\epsilon$ and the normal
property does not hold in $p^{\prime}$ (Fig. 8). Since in $p^{\prime}$ the
normal property does not hold, there is some subpath $\rho$ of
$\sigma(s,p^{\prime})$ or $\sigma(p^{\prime},t)$ that lies in the positive or
negative half-plane defined by the normal through $h_{p}^{\prime}$,
respectively. Furthermore, the normal $h_{p}$ touches $\sigma$ at some point
$q\in\rho$. However, if $p$ does not exist, there exists a bend point $b$ such
that there are two lines $h^{\prime}_{b},h^{\prime\prime}_{b}\in h_{b}$ among
the set of lines in the normal $h_{b}$, such that $h^{\prime}_{b}$ touches
$\sigma$ at some point $q\in\sigma$ and $h^{\prime\prime}_{b}$ intersects
$\sigma$ (Fig. 8). All cases where $p$ does not exist are simply analogous to
the cases where $p$ exists. Therefore, we will only cover the cases where $p$
exists.

We assume, without loss of generality, that line segment $\overline{pq}$ is
horizontal, $p$ lies to the right of $q$, and $\sigma(s,p)$ lies above
$h_{p}$. Let $e$ be the segment of $\sigma$ containing $p$ and $f$ be the
segment of $\sigma$ containing $q$. We must consider the cases where
$q\in\sigma(s,p)$ and $q\in\sigma(p,t)$. Furthermore, since $\sigma$ is a
geodesic in $P\setminus(\mathcal{D}_{t}\cup\mathcal{D}_{s})$ the segments $e$
and $f$ can be straight line segments, or boundaries of a dead region of
$\mathcal{D}_{t}$ or $\mathcal{D}_{s}$. If $f$ is a straight line segment,
then $q$ must be an end point of $f$ and thus be a vertex of polygon $P$.
Here, we will only cover the case where $q\in\sigma(s,p)$, $e$ is a boundary
of $\mathcal{D}_{t}$, and $q$ is a vertex of $P$. For each possible
combination of the segment types of $e$ and $f$ and the location of $q$ on the
path $\sigma$ we show that these cases are not possible by contradiction.

Once we have shown that no point exists where the normal property is violated,
$\sigma$ indeed has increasing chords by Lemma 1. Furthermore, $\sigma$ must
be the shortest path with increasing chords. Any path that is shorter than
$\sigma$ must go through either of the dead regions $\mathcal{D}_{t}$ or
$\mathcal{D}_{s}$. Therefore, any path shorter than $\sigma$ cannot have
increasing chords and $\sigma$ must be the shortest path with increasing
chords.

(a) The point of curvature of $\sigma$ at point $p$ lies to the right of $p$.

(b) The point of curvature $v$ of $\sigma$ at point $p$ lies to the left of
$p$. The green path is the shortest self-approaching $p$-$t$ path.

(c) The point of curvature $v$ of $\sigma$ at point $p$ lies to the left of
$p$. The orange path is the shortest self-approaching $v$-$s$ path, that
intersects with $h_{p}$ in $w$ and $w^{\prime}$.

Figure 9: Geodesic $\sigma$ (purple) where point $q\in\sigma(s,p)$, $p$ lies
on a boundary of $\mathcal{D}_{t}$ (red), and $q$ is a vertex of $P$.

#### Point $q\in\sigma(s,p)$, $e$ is a boundary of $\mathcal{D}_{t}$, and $q$
is a vertex of $P$ (Fig. 9)

The center of curvature of $\sigma$ at $p$ must lie to the left of $p$.
Otherwise the normal $h_{p^{\prime}}$ to $\sigma$ cannot intersect
$\sigma(s,p)$, as is depicted in Fig. 9(a). Let $\pi_{pt}$ be the shortest
self-approaching path from $p$ to $t$. Segment $e$ is part of
$\mathcal{D}_{t}$, therefore there must be a point $v\in\pi_{pt}$ touched by
normal $h_{p}$ (Fig. 9(b)). Because $\pi_{pt}$ goes through $v$, $h_{v}$ is
perpendicular to $h_{p}$ (if $v$ is a bend point, then there must be a line
which is perpendicular $h_{p}$ in the set of normals $h_{v}$). Furthermore,
$\pi_{pt}(v,t)$ lies completely in the positive half-plane $h_{v}^{+}$ by the
half-plane property. We will now show that in the region between
$\overline{pv}$ and $\pi_{pt}(p,v)$ there are vertices of $P$. The straight
line segment $\overline{pv}$ concatenated to $\pi_{pt}(v,t)$ would be self-
approaching. However, $p^{\prime}$ lies below $h_{p}$, thus polygon $P$ must
intersect with $\overline{vp}$. Therefore, the shortest self-approaching
$v$-$s$ path $\pi_{vs}$ must first intersect or touch $h_{p}$ to the right of
$v$ at point $w$ and later to the left of $v$ at point $w^{\prime}$ (Fig.
9(c)). Thus, $|vw^{\prime}|<|ww^{\prime}|$ which contradicts the self-
approaching property of $\pi_{vs}$. Hence, this case is not possible if the
geodesic between $s$ and $t$ exists.

Figure 10: Point $q\in\sigma(s,p)$, $p$ lies on a boundary of
$\mathcal{D}_{t}$ (red), and $q$ lies on a boundary of $\mathcal{D}_{s}$
(blue). The green path is the shortest self-approaching $p$-$t$ path.

Figure 11: Point $q\in\sigma(s,p)$, and both $p$ and $q$ lie on a boundary of
$\mathcal{D}_{t}$ (red). The green path is the shortest self-approaching
$q$-$t$ path.

#### Case 2: $q\in\sigma(s,p)$, $e$ is a boundary of $\mathcal{D}_{t}$, and
$f$ is a boundary of $\mathcal{D}_{s}$ (Fig. 11)

This case is analogous to Case 1 (Fig. 9).

#### Case 3: $q\in\sigma(s,p)$, $e$ is a boundary of $\mathcal{D}_{t}$, and
$f$ is a boundary of $\mathcal{D}_{t}$ (Fig. 11)

Since $q$ is touched by $h_{p}$ and $q$ lies on a boundary of
$\mathcal{D}_{t}$, normal $h_{q}$ is perpendicular to $h_{p}$. Furthermore,
consider shortest self-approaching $q$-$t$ path $\pi_{qt}$. Because $q$ lies
on a boundary of $\mathcal{D}_{t}$ there is a point $v\in\pi_{qt}$ touched by
$h_{q}$ with $h_{v}\bot h_{q}$. Path $\pi_{qt}(p,t)$ or $\pi_{qt}(v,t)$ must
lie both in $h_{v}^{+}$ and in $h_{p}^{+}$, however the intersection of these
half-planes is empty; $h_{v}^{+}\cap h_{p}^{+}=\emptyset$. Hence, path
$\pi_{qt}$ cannot exist.

Figure 12: Point $q\in\sigma(s,p)$ and $p$ lies on a straight line segment
(orange).

Figure 13: Point $q\in\sigma(s,p)$, $p$ lies on a boundary of
$\mathcal{D}_{s}$ (blue), and $q$ is a vertex of $P$.

#### Case 4: $q\in\sigma(s,p)$ and $e$ is a straight line segment (Fig. 13)

Since the normals $h_{p}$ and $h_{p^{\prime}}$ are parallel it is impossible
for $h_{p^{\prime}}$ to be able to intersect with $\sigma(s,p)$.

#### Case 5: $q\in\sigma(s,p)$, $e$ is a boundary of $\mathcal{D}_{s}$, and
$q$ is a vertex of $P$ (Fig. 13)

Normal $h_{p}$ touches $\sigma(s,p)$ at point $q$. Point $q$ does not lie in
the positive half-plane $h_{p^{\prime}}^{+}$ of the shortest self-approaching
$p^{\prime}$-$s$ path $\pi_{p^{\prime}s}$. Since $q$ is a vertex of $P$,
$h_{p^{\prime}}$ intersects with $P$. Therefore, $s$ and $p^{\prime}$ must lie
in different connected components in the intersection of $P$ and the positive
half-plane $h_{p^{\prime}}^{+}$ of the path $\pi_{p^{\prime}s}$. Hence, no
$p^{\prime}$-$s$ path can exist including $\pi_{p^{\prime}s}$.

Figure 14: Point $q\in\sigma(s,p)$, and both $p$ and $q$ lie on a boundary of
$\mathcal{D}_{s}$ (blue).

Figure 15: Point $q\in\sigma(s,p)$, $p$ lies on a boundary of
$\mathcal{D}_{s}$ (blue), and $q$ lies on a boundary of $\mathcal{D}_{t}$
(red). The green path is the shortest self-approaching $q$-$t$ path.

#### Case 6: $q\in\sigma(s,p)$, $e$ is a boundary of $\mathcal{D}_{s}$, and
$q$ is a boundary of $\mathcal{D}_{s}$ (Fig. 15).

Normal $h_{p}$ touches $\sigma(s,p)$ at point $q$. Point $q$ does not lie in
the positive half-plane $h_{p^{\prime}}^{+}$ of the shortest self-approaching
$p^{\prime}$-$s$ path $\pi_{p^{\prime}s}$. Since $q$ lies on a boundary of
$\mathcal{D}_{s}$, $h_{p^{\prime}}$ intersects with this boundary. Therefore,
$s$ and $p^{\prime}$ must lie in different connected components in the
intersection of $P\setminus\mathcal{D}_{s}$ and the positive half-plane
$h_{p^{\prime}}^{+}$ of the path $\pi_{p^{\prime}s}$. Hence,
$\pi_{p^{\prime}s}$ cannot exist.

#### Case 7: $q\in\sigma(s,p)$, $e$ is a boundary of $\mathcal{D}_{s}$, and
$f$ is a boundary of $\mathcal{D}_{t}$ (Fig. 15)

This case is analogous to Case 3 (Fig. 11).

Figure 16: Point $q\in\sigma(p,t)$, $p$ lies on a boundary of
$\mathcal{D}_{t}$ (red), and $q$ is a vertex of $P$.

Figure 17: Point $q\in\sigma(p,t)$, and both $p$ and $q$ lie on a boundary of
$\mathcal{D}_{t}$ (red).

#### Case 8: $q\in\sigma(p,t)$, $e$ is a boundary of $\mathcal{D}_{t}$, and
$q$ is a vertex of $P$ (Fig. 17)

This case is analogous to Case 5 (Fig. 13).

#### Case 9: $q\in\sigma(p,t)$, $e$ is a boundary of $\mathcal{D}_{t}$, and
$f$ is a boundary of $\mathcal{D}_{t}$ (Fig. 17)

This case is analogous to Case 6 (Fig. 15).

Figure 18: Point $q\in\sigma(p,t)$, $p$ lies on a boundary of
$\mathcal{D}_{t}$ (red), and $q$ lies on a boundary of $\mathcal{D}_{s}$
(blue). The orange path is the shortest self-approaching $q$-$s$ path.

Figure 19: Point $q\in\sigma(p,t)$, both $p$ and $q$ lie on a straight line
segment (orange), and point $w$ lies on boundary $d$ of $\mathcal{D}_{s}$
(blue) with $h_{p}\parallel h_{w}$. The green path is the shortest self-
approaching $p$-$t$ path.

#### Case 10: $q\in\sigma(p,t)$, $e$ is a boundary of $\mathcal{D}_{t}$, and
$f$ is a boundary of $\mathcal{D}_{s}$ (Fig. 19)

Point $s$ must lie above $h_{p}$ as in $p$ the normal property is not yet
violated. Furthermore, the point of curvature $v$ of $\sigma$ at point $q$
must lie below $h_{q}$. The shortest self-approaching $q$-$s$ path $\pi_{qs}$
must travel through $v$ and because $h_{q}$ touches this point, there is a
normal $h_{v}$ that is parallel to $h_{p}$. Point $s$ cannot lie above $h_{p}$
and below $h_{v}$ at the same time, hence this construction cannot exist.

Figure 20: The disc with radius $|pq^{\prime}|$ centered at point $q^{\prime}$
which lies on the straight line segment $\overline{pq}$ is fully contained in
the disc with radius $|pq|$ centered at $q$.

#### Case 11: $q\in\sigma(p,t)$, $e$ is a straight line segment, and $q$ a
vertex of $P$ (Fig. 19)

The normal $h_{p}$ touches $\sigma(p,t)$ at point $q$ which is a vertex of
$P$. The shortest self-approaching $p$-$t$ path $\pi_{pt}$ must intersect or
touch $h_{p}$ at least once in point $q^{\prime}$ that lies between $p$ and
$q$. By definition we know that $|pq^{\prime}|\geq|vq^{\prime}|$ for every
point $v$ of $\pi_{pt}(p,q^{\prime})$. Therefore, $|pq|\geq|vq|$, i.e. every
point of the subpath $\pi_{pt}(p,q^{\prime})$ lies in a disc centered at $q$
with radius $|pq|$ (Fig. 20). Thus, the straight line segment $e$ is not part
of $\pi_{pt}$ and $e$ is a part of $\sigma$ due to a boundary $d$ of
$\mathcal{D}_{s}$. Segment $e$ can only be part of $\sigma$ if there is a
point $w\in d\subset\sigma$ with a normal $h_{w}$ that is parallel to $h_{p}$
and $\sigma(p,w)$ only contains straight line segments and boundaries of
$\mathcal{D}_{s}$. Otherwise, at the end of $e$ there is either a bend point
where $\sigma$ turns to the right or $e$ is tangent to a boundary of
$\mathcal{D}_{t}$. In either option, no self-approaching $p$-$t$ path can
exist. Since $w$ lies on a boundary of $\mathcal{D}_{s}$, there must be a
point $w^{\prime}$ on the shortest self-approaching $w$-$s$ path $\pi_{ws}$
touched by $h_{w}$. Therefore, $\sigma(s,w)$ must intersect or touch $h_{w}$
too. However, $\sigma(s,w)$ cannot intersect $h_{w}$ as in $h_{p}$ the normal
property is not violated, thus $\sigma$ cannot exist.

Figure 21: Point $q\in\sigma(p,t)$, $p$ lies on a straight line segment
(orange), and $q$ lies on a boundary of $\mathcal{D}_{t}$ (red). The green
path is the shortest self-approaching $p$-$t$ path.

Figure 22: Point $q\in\sigma(p,t)$, $p$ lies on a straight line segment
(orange), and $q$ lies on a boundary of $\mathcal{D}_{s}$ (blue). The orange
path is the shortest self-approaching $q$-$s$ path.

#### Case 12: $q\in\sigma(p,t)$, $e$ is a straight line segment, and $f$ a
boundary of $\mathcal{D}_{t}$ (Fig. 22)

This case is analogous to Case 11 (Fig. 19).

#### Case 13: $q\in\sigma(p,t)$, $e$ is a straight line segment, and $f$ a
boundary of $\mathcal{D}_{s}$ (Fig. 22)

Point $s$ must lie above $h_{p}$ as in $p$ the normal property is not yet
violated. Furthermore, the center of curvature $v$ of $\sigma$ at point $q$
must lie below $h_{p}$. The shortest self-approaching $q$-$s$ path $\pi_{qs}$
must travel through $v$ and because $h_{q}$ touches this point, there is a
normal $h_{v}$ that is parallel to $h_{p}$. Point $s$ cannot lie above $h_{p}$
and below $h_{v}$ at the same time, hence this construction cannot exist.

(a) The point of curvature of $\sigma$ at $p$ lies in the direction of $q$.
The orange path is the shortest self-approaching $q$-$s$ path.

(b) Point of curvature of $\sigma$ at $p$ lies in the opposite direction of
$q$. The green path is the shortest self-approaching $p$-$t$ path.

Figure 23: Point $q\in\sigma(p,t)$, $q$ is a vertex of $P$, and $p$ lies on a
boundary of $\mathcal{D}_{s}$ (blue).

#### Case 14: $q\in\sigma(p,t)$, $e$ is a boundary of $\mathcal{D}_{s}$, and
$q$ is a vertex of $P$ (Fig. 23)

There are two cases that need to be considered, either the point $v$ of
$\sigma$ at point $p$ lies in the direction of $q$ with respect to $p$ or not.
First we consider the case where $v$ lies in the direction of $q$ (Fig.
23(a)). Since $q$ lies in the negative half-plane $h_{p^{\prime}}^{-}$, the
center of curvature of $\sigma$ at point $p$ must lie to the left of $q$.
Therefore, the shortest self-approaching $q$-$s$ path $\pi_{qs}$ must first
intersect or touch $h_{p}$ to the right of $q$ at point $w$ and later to the
left at point $w^{\prime}$. Thus, $|qw^{\prime}|<|ww^{\prime}|$ which
contradicts the self-approaching property of $\pi_{vs}$.

The case where $v$ does not lie in the direction of $q$ with respect to $p$
(Fig. 23(b)) is analogous to Case 11 (Fig. 19).

Figure 24: Point $q\in\sigma(p,t)$, $q$ lies on a boundary of
$\mathcal{D}_{t}$ (red), and $p$ lies on a boundary of $\mathcal{D}_{s}$
(blue).

Figure 25: Point $q\in\sigma(p,t)$, $q$ lies on a boundary of
$\mathcal{D}_{s}$ (blue), and $p$ lies on a boundary of $\mathcal{D}_{s}$
(blue). The orange path is the shortest self-approaching $q$-$s$ path.

#### Case 15: $q\in\sigma(p,t)$, $e$ is a boundary of $\mathcal{D}_{s}$, and
$f$ is a boundary of $\mathcal{D}_{t}$ (Fig. 25)

This case is analogous to Case 14 (Fig. 23).

#### Case 16: $q\in\sigma(p,t)$, $e$ is a boundary of $\mathcal{D}_{s}$, and
$f$ is a boundary of $\mathcal{D}_{s}$ (Fig. 25)

Point $s$ must lie above $h_{p}$ as in $p$ the normal property is not yet
violated. Furthermore, the point of curvature $v$ of $\sigma$ at point $q$
must lie below $h_{q}$. The shortest self-approaching $q$-$s$ path $\pi_{qs}$
must travel through $v$ and because $h_{q}$ touches this point, there is a
normal $h_{v}$ that is parallel to $h_{p}$. Point $s$ cannot lie above $h_{p}$
and below $h_{v}$ at the same time, hence this construction cannot exist. ∎

Figure 26: Polygon $P$ with dead regions $\mathcal{D}_{s}$ (red) and
$\mathcal{D}_{t}$ (blue), the geodesic (purple) of the remaining area is the
shortest path with increasing chords.

Using Theorem 6, the shortest $s$-$t$ path with increasing chords in a polygon
$P$ can be found by subtracting the dead regions $\mathcal{D}_{t}$ and
$\mathcal{D}_{s}$ from polygon $P$ (Fig. 26). Therefore, this shortest path
with increasing chords can be found in a similar manner to finding the
shortest self-approaching $s$-$t$ path as described by Bose et al. [3]. As is
the case for the algorithm for the shortest self-approaching path, the
shortest path with increasing chords can only be found if we assume that
transcendental equations can be solved or that an approximation of the path
will be calculated.

##  4 Conclusions

In this paper, we showed that the shortest $s$-$t$ path with increasing chords
in a simple polygon is unique. Furthermore, we showed that the shortest
$s$-$t$ path in a polygon minus the dead regions of $s$ and $t$ is the
shortest path with increasing chords. Therefore, the algorithm for finding the
shortest path with increasing chords is similar to finding a shortest self-
approaching path.

A natural direction for future research is the question of whether an
efficient algorithm exists that can find a shortest $s$-$t$ path with
increasing chords in a polygon with holes. The possibility remains open that
this problem is NP-hard.

## References

  * [1] M. Biro, J. Gao, J. Iwerks, I. Kostitsyna, and J.S.B. Mitchell.  Beacon-based routing and coverage.  In 21st Fall Workshop on Computational Geometry (FWCG 2011), 2011\.
  * [2] M. Biro, J. Gao, J. Iwerks, I. Kostitsyna, and J.S.B. Mitchell.  Combinatorics of beacon-based routing and coverage.  In Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG), pages 1–6, 2013.  URL: https://cs.uwaterloo.ca/conferences/cccg2013/.
  * [3] P. Bose, I. Kostitsyna, and S. Langerman.  Self-approaching paths in simple polygons.  Computational Geometry, 87, 2020.  doi:10.1016/j.comgeo.2019.101595.
  * [4] J. Gao and L. Guibas.  Geometric algorithms for sensor networks.  Philosophical transactions. Series A, Mathematical, physical, and engineering sciences, 370:27–51, 2012.  doi:10.1098/rsta.2011.0215.
  * [5] C. Icking, R. Klein, and E. Langetepe.  Self-approaching curves.  Mathematical Proceedings of the Cambridge Philosophical Society, 125, 05 2002.  doi:10.1017/S0305004198003016.
  * [6] D.G. Larman and P. McMullen.  Arcs with increasing chords.  Mathematical Proceedings of the Cambridge Philosophical Society, 72(2):205–207, 1972.  doi:10.1017/S0305004100047022.
  * [7] G. Rote.  Curves with increasing chords.  In Mathematical Proceedings of the Cambridge Philosophical Society, volume 115, pages 1–12. Cambridge University Press, 1994.