# On Flipping the Fréchet distance

Omrit Filtser  The Open University of Israel
<EMAIL_ADDRESS>Mayank Goswami This work is supported by US National
Science Foundation (NSF) awards CRII-1755791 and CCF-1910873. Queens College
CUNY
<EMAIL_ADDRESS>Joseph S.B.Mitchell This work is partially
supported by the National Science Foundation (CCF-2007275), the US-Israel
Binational Science Foundation (BSF project 2016116), Sandia National Labs, and
DARPA (Lagrange). Stony Brook University
<EMAIL_ADDRESS>Valentin Polishchuk  Linköping University
<EMAIL_ADDRESS>
###### Abstract

The classical and extensively-studied Fréchet distance between two curves is
defined as an _inf max_ , where the infimum is over all traversals of the
curves, and the maximum is over all concurrent positions of the two agents. In
this article we investigate a “flipped” Fréchet measure defined by a _sup min_
– the supremum is over all traversals of the curves, and the minimum is over
all concurrent positions of the two agents. This measure produces a notion of
“social distance” between two curves (or general domains), where agents
traverse curves while trying to stay as far apart as possible.

We first study the flipped Fréchet measure between two polygonal curves in one
and two dimensions, providing conditional lower bounds and matching
algorithms. We then consider this measure on polygons, where it denotes the
minimum distance that two agents can maintain while restricted to travel in or
on the boundary of the same polygon. We investigate several variants of the
problem in this setting, for some of which we provide linear time algorithms.
Finally, we consider this measure on graphs.

We draw connections between our proposed flipped Fréchet measure and existing
related work in computational geometry, hoping that our new measure may spawn
investigations akin to those performed for the Fréchet distance, and into
further interesting problems that arise.

###### Contents

  1. 1 Introduction
  2. 2 Flipped Fréchet measure on polygonal curves
    1. 2.1 A near linear time algorithm for FF in 1D
    2. 2.2 Quadratic time algorithms
    3. 2.3 Quadratic lower bounds
    4. 2.4 More than 2 agents
  3. 3 Social distancing in a simple polygon
    1. 3.1 Red on an arbitrary path mission
    2. 3.2 Red on a shortest path mission
    3. 3.3 SDW of closed curves and polygons
    4. 3.4 Social distancing in a skinny polygon (or a tree)
  4. 4 Social distancing on graphs
    1. 4.1 Abstract Graphs
    2. 4.2 Geometric Graphs

##  1 Introduction

The classical Fréchet distance between two curves $P$ and $Q$ is defined as
the minimum length of a leash required for a person to walk their dog, with
the person and the dog traversing $P$ and $Q$ from start to finish,
respectively. Inspired by the challenge of maintaining social distancing among
groups and individuals, we consider the question of developing a notion
opposite to the Fréchet distance, where instead of keeping the agents close
(short leash), we keep them as far apart as possible.

In this paper we propose a new measure, called the _Flipped Fréchet_ measure,
to capture the amount of social distancing possible while traversing two
curves. While Fréchet distance is defined as an _inf max_ , where the infimum
is over all traversals of the curves, and the maximum is over all concurrent
positions of the two agents, the flipped Fréchet measure111One observes that
this measure is not a metric/distance as it does not satisfy the triangle
inequality. is defined as a _sup min_ – the supremum is over all traversals of
the curves, and the minimum is over all concurrent positions of the two
agents. How efficiently can this measure be computed, for curves in one or two
dimensions? What if the two agents are walking on edges of a graph, which may
or may not be embedded in the plane? Such questions have been considered for
Fréchet distance, and in this paper we initiate their study for the flipped
Fréchet measure.

We refer to the two agents as “Red” and “Blue” henceforth. Considering the
social distancing problem further, what if Blue is not restricted to move
along some given curve; rather, it can choose its own path? We now start
arriving at a class of problems that have no analogues in the Fréchet version.
Of course, if Blue had no restrictions at all, it could just go to infinity
and thus be far from Red (on any path). It therefore makes sense to restrict
the domain for Blue, e.g. to a simple polygon $P$ in which Red is traveling,
and measure separation using geodesic distance in $P$. We consider questions
regarding the complexity of calculating a strategy for Blue to stay away from
Red, when Red is traveling on a given path, which may or not be a geodesic in
$P$.

An architect designing spaces within a building is faced with choices about
the shapes of these spaces, where one must choose, say, between two polygons
$P$ and $Q$ where agents will move, in hopes to maximize the potential for
social distancing. In order to do so, it would be useful to have a notion of a
“social distancing width” of a polygon, that captures the difficulty or ease
with which two agents can move around in a polygon while maintaining
separation. Consider a simple polygon $P$ where the Red agent is on a mission
to follow a path, e.g. to traverse the boundary of $P$, while the Blue agent
moves within $P$ (with a starting point of Blue’s choice), in order to
maximize the minimum Red-Blue distance. We define the social distance width
(SDW for short) of a polygon $P$ to be the minimum Red-Blue distance that can
be maintained throughout the movement, maximized over all possible movement
strategies, and study algorithms to compute the SDW of a polygon.

For all of the above problems, in addition to developing algorithms for the
general versions, we also consider special scenarios which facilitate faster
algorithms; for example, while our algorithm for computing the SDW for general
polygons runs in quadratic time, we show that for skinny polygons (or a tree),
one can compute the SDW in linear time.

Although this article mostly considers the above problems in the case of $k=2$
agents, in general one may be given $k$ agents and $k$ associated domains.
Each agent is restricted to move only within its respective domain, and at
least one of the agents has some mission, e.g., to move from a given start
point to a given end point, or to traverse a given path inside the domain. In
addition, the domains may be shared or distinct, and different agents may have
different speeds. The goal is to find a movement strategy for all the agents,
such that the _minimum pairwise_ distance between the agents at any time is
maximized. Additionally, one may seek to minimize the time necessary to
complete one or more missions.

This new class of problems is different from the usual motion planning
problems between robots, or disjoint disks, in some fundamental aspects. Most,
if not all, literature on robot motion planning assumes robots are cooperating
on some task. One then considers optimizing objectives like makespan, or total
distance travelled, etc. However, the kind of movement we consider is far from
cooperative – in fact, some agents may not care about social distancing, while
others do. Some may be “on a mission” while others are just trying to maintain
a safe distance. In addition, different agents may have different starting
times and deadlines. Furthermore, as mentioned above, one also encounters
design problems, where one may want to configure a layout of a building, a
floor plan, or designate rules for traffic flow, in order to facilitate social
distancing.

Related Work. The Fréchet distance is an extensively investigated distance
measure for curves, starting with the early work of Alt and Godau [AG95] in
’95. There is a quadratic-time algorithm for computing it [EM94, AG95], and it
was recently shown [Bri14] that under the Strong Exponential Time Hypothesis
(SETH), no subquadratic algorithm exists, not even in one dimension [BM16].
Moreover, under SETH, no subquadratic algorithm exists for approximating the
Fréchet distance within a factor of 3 [BOS19].

The problem of coordinating collision-free motion of two agents traveling on
polygonal curves was considered already in ’89 by O‘Donnell and Lozano-Perez
[OL89], in the context of robot manipulators. Assuming some additional
restrictions on the movements of the agents (e.g. robots are not allowed to
simultaneously traverse segments that are too close), they give an
$O(n^{2}\log n)$ algorithm for minimizing the completion time.

There is an extensive literature on related problems of motion planning in
robotics. Perhaps most closely related to our work is that of coordinated
motion planning of 2 or more disks; see [DFK+19], on nearly optimal (in terms
of lengths of motions) rearrangements of multiple unit disks and the related
work of [HH02]. (In our problems, instead of minimizing length of motion for
given radius disks, we seek to maximize the radii.)

The problem of computing safe paths for multiple speed-bounded mobile agents
that must maintain separation standards arises in air traffic management (ATM)
and Aircraft/Train Scheduling applications. [AMP10] studied the problem of
computing a large number of “thick paths” for multiple speed-bounded agents,
from a source region to a sink region, where the thickness of a path models
the separation standard between agents, and the objectives are to obey speed
bounds, maintain separation, and maximize throughput. In the Aircraft/Train
Scheduling problem (see [DFK+19, Sch20a, Sch20b]), given a set of paths on
which the agents travel, and a separation parameter, the goal is to find a
collision-free motion of the agents while minimizing the time of completion.
(In our problems, we are not maximizing a “throughput” or makespan; rather, we
maximize a separation standard, for a given set of agents.)

In the maximum dispersion problem, the goal is to place $n$ (static) points
within a domain $P$ in order to maximize the minimum distance between two
points. (Optionally, one may also seek to keep points away from the boundary
of $P$.) An optimal solution provides maximum social distancing for a set of
static agents, who stand at the points, without moving. Constant factor
approximation algorithms are known [BF01, FM04]. (The problem is also closely
related to geometric packing problems, which is a subfield in itself.) In
robotics, the problem of motion planning in order to achieve well dispersed
agents has also been studied: move a swarm of robots, through “doorways”, into
a geometric domain, in order to achieve a set of agents well dispersed
throughout the domain. Such movements can be accomplished [HAB+02] using local
strategies that are provably competitive.

In the adversarial setting, in which one or more agents is attempting to move
in order to avoid (evade) a pursuer, there is considerable work on pursuit-
evasion in geometric domains (e.g., the “lion and man” problem); see the
survey [CHI11].

Our results. In this paper, we (mostly) consider the case of $k=2$, i.e., two
agents, “Red” and “Blue”, that move inside their given domains. Further, in
this paper, unless stated otherwise, we do not consider speed to be a limiting
factor; e.g., when Blue moves in order to maintain distance from Red, we
assume that Blue can move at a sufficient speed.

We begin by considering the scenario in which the two domains are polygonal
curves $R$ and $B$. The agents’ missions are to traverse their respective
curves, from the start point to the end point, in order to maximize the
minimum distance between the agents. The Flipped Fréchet measure between the
two curves is the maximum separation that can be maintained. In Section 2 we
consider both the continuous case (agents move continuously along the edges of
their curves), and the discrete case (agents “jump” between consecutive
vertices of their curves). We first show that the Flipped Fréchet measure
between two $n$-vertex curves in one dimension (1D) can be computed in near-
linear time. This is in sharp contrast with continuous Fréchet distance, which
has quadratic conditional (SETH-based) lower bounds [BM16]. We then develop
quadratic or near-quadratic time algorithms for computation of discrete
Flipped Fréchet measure in 1D and 2D, and for 2D continuous Flipped Fréchet
measure. We also complement our quadratic-time algorithms with conditional
lower bounds (conditioned on the Orthogonal vectors (OV) problem), even for
approximation: we give a quadratic conditional lower bound on approximating
SDW for curves in 2D up to a factor better than $\frac{\sqrt{5}}{2\sqrt{2}}$,
and a quadratic conditional lower bound on approximating discrete SDW for
curves in 1D, with a factor better than $\frac{2}{3}$.

We then restrict the domain for Blue to a simple polygon $P$, and measure
separation using geodesic distance in $P$. In Section 3 we consider several
versions. In the first, the Red agent has a mission to walk along an arbitrary
path inside the polygon. The Blue agent must stay as far as possible from Red,
and the only restriction is to move inside $P$. This is related to the motion
planning problem in which we are given a set of disjoint bodies (e.g., disks),
and we seek a motion plan that allows them to remain disjoint while each moves
to a destination. We give a quadratic time algorithm for this problem. We then
show that under the reasonable assumption that Red moves on a geodesic, one
can compute a strategy for Blue in near linear time.

Next, we consider a simple polygon $P$ where the Red agent is on a mission to
traverse the boundary of $P$, while the Blue agent moves within $P$ (with a
starting point of Blue’s choice), in order to maximize the minimum Red-Blue
distance. We define the social distance width (SDW for short) of a polygon $P$
to be the minimum Red-Blue distance that can be maintained throughout the
movement, maximized over all possible movement strategies. We develop
quadratic time algorithm to compute the SDW of a polygon, but show that when
$P$ is a skinny polygon (a tree), a strategy for Blue can be computed in
linear time. The discussion on this special case of trees leads us to
investigating the more general case where agents are walking on a graph (which
may or may not be embedded in the plane). In section 4 we define the notion of
Social Distance Width of two graph, and show how to compute it.

##  2 Flipped Fréchet measure on polygonal curves

In this section the domains of Red and Blue are two polygonal curves $R$ and
$B$, respectively. We begin by giving some basic definitions; then, we
describe tools that were used in classic algorithms for Fréchet distance and
the relation to the social distancing problem for curves.

A polygonal curve $P$ in ${\mathbb{R}}^{d}$ is a continuous function
$P:[1,n]\rightarrow{\mathbb{R}}^{d}$, such that for any integer $1\leq i\leq
n-1$ the restriction of $P$ to the interval $[i,i+1]$ forms a line segment. We
call the points $P[1],P[2],\dots,P[n]$ the vertices of $P$, and say that $n$
is the length of $P$. For any real numbers $\alpha,\beta\in[1,n]$,
$\alpha\leq\beta$, we denote by $P[\alpha,\beta]$ the restriction of $P$ to
the interval $[\alpha,\beta]$. Then, for any integer $1\leq i\leq n-1$,
$P[i,i+1]$ is an edge of $P$. A continuous, non-decreasing, surjective
function $f:[0,1]\rightarrow[1,n]$ is called a _traversal_ of $P$.

Let $P:[1,n]\rightarrow{\mathbb{R}}^{d}$ and
$Q:[1,m]\rightarrow{\mathbb{R}}^{d}$ be two polygonal curves. A _traversal_ of
$P$ and $Q$ is a pair $\tau=(f,g)$, with $f:[0,1]\rightarrow[1,n]$ a traversal
of $P$, $g:[0,1]\rightarrow[1,m]$ a traversal of $Q$.

######  Definition 1 (Flipped Fréchet Measure).

The _(Flipped Fréchet measure_ (FF) of $P$ and $Q$ is $\displaystyle
FF(P,Q)=\sup_{\tau=(f,g)}\min_{t\in[0,1]}\|P(f(t))-Q(g(t))\|.$

Note that the well-studied _Fréchet distance_ between $P$ and $Q$ is
$\inf_{\tau=(f,g)}\max_{t\in[0,1]}\|P(f(t))-Q(g(t))\|$, where $\tau$ is a
traversal of $P$ and $Q$.

The discrete case. When considering discrete polygonal curves, we simply
define a polygonal curve $P$ as a sequence of $n$ points in
${\mathbb{R}}^{d}$. We denote by $P[1],\dots,P[n]$ the vertices of $P$, and
for any $1\leq i\leq j\leq n$ let $P[i,j]=(P[i],P[i+1],\dots,P[j])$ be a
subcurve of $P$.

Consider two sequences of points $P,Q$ of length $n$ and $m$, respectively. A
_traversal_ $\tau$ of $P$ and $Q$ is a sequence,
$(i_{1},j_{1}),\dots,(i_{t},j_{t})$, of pairs of indices such that
$i_{1}=j_{1}=1$, $i_{t}=n$, $j_{t}=m$, and for any pair $(i,j)$ it holds that
the following pair is $(i,j+1)$, $(i+1,j)$, or $(i+1,j+1)$.

######  Definition 2 (Discrete Flipped Fréchet Measure).

The _discrete Flipped Fréchet measure_ (dFF) of $P$ and $Q$ is $\displaystyle
dFF(P,Q)=\max_{\tau}\min_{(i,j)\in\tau}\|P[i]-Q[j]\|.$

Notice that unlike in the continuous case, the distances between the agents
are only calculated at the vertices of the polygonal curves.

The _discrete Fréchet distance_ (DFD) between $P$ and $Q$ is
${\min_{\tau}\max_{(i,j)\in\tau}\|P[i]-Q[j]\|}$, and it can be computed in
$O(nm)$ time [EM94] using a simple dynamic programming algorithm.

From now on, we assume for simplicity that both curves $R$ and $B$ have length
$n$; however, our algorithms and proofs can be easily adapted to the general
case of $m\neq n$.

We give (Section 2.1) a near-linear algorithm to compute the continuous FF
measure in 1D, demonstrating that “flipping” the objective function makes this
setting easier: for continuous Fréchet there exist conditional quadratic lower
bounds [BM16]. We give quadratic algorithms and then conditional lower bounds
(Sections 2.2 and 2.3) for computing or approximating other variants (1D
discrete, 2D continuous and discrete) of FF measure, specifically:

  * •

a quadratic lower bound, conditioned on the Strong Exponential Time Hypothesis
(SETH), on approximating FF measure for curves in 2D, with approximation
factor $\frac{\sqrt{5}}{2\sqrt{2}}$.

  * •

a quadratic lower bound, conditioned on the Strong Exponential Time Hypothesis
(SETH), on approximating dFF measure for 1D curves, with approximation factor
$\frac{2}{3}$.

###  2.1 A near linear time algorithm for FF in 1D

Consider the decision version of FF in 1D: Given two paths, $R$ and $B$, on
the $x$-axis, each specified by $n$ points, we are to determine if it is
possible to find a traversal of the two paths so that Red and Blue maintain
separation larger than $\delta$ during their traversals. We assume, w.l.o.g.,
that $R[1]<B[1]$. We can also assume that $B[1]-R[1]>\delta$, as otherwise we
can simply return NO. Notice that it suffices to consider the problem of
maintaining separation at least 0 between $R$ and a shifted (by $\delta$) copy
of $B$; we seek to determine if $FF(B,R)>0$. Let $b_{\max}$ be the rightmost
point of $B$ and let $r_{\min}$ be the leftmost point of $R$.

######  Lemma 3.

If $FF(B,R)>0$, then:

  1. (i)

All of $R$ must be to the left of $b_{\max}$, and all of $B$ must be to the
right of $r_{\min}$.

  2. (ii)

While Blue is at $b_{\max}$, any subpath of $R$ can be traversed by Red. While
Red is at $r_{\min}$, any subpath of $B$ can be traversed by Blue.

  3. (iii)

There exists a traversal achieving $FF(B,R)>0$ such that at some point Blue is
at $b_{\max}$ and Red is at $r_{\min}$.

###### Proof.

(i) holds by continuity: if $R$ has a point to the right of $b_{\max}$, Red
must cross Blue before getting to that point. The claim for $B$ is symmetric.
(ii) then follows from (i).

For (iii), consider a traversal $\tau$, and assume that Blue reaches
$b_{\max}$ before Red reached $r_{\min}$. Let $r^{\prime}$ be the location of
Red when Blue is at $b_{\max}$; $r^{\prime}$ does not have to a be a vertex of
$R$, but in any case $r^{\prime}$ precedes $r_{\min}$ along $R$. Let
$b^{\prime}\in B$ be Blue’s location at the time Red reaches $r_{\min}$
($b^{\prime}$ is after $b_{\max}$). By (ii), while Blue is at $b_{\max}$, Red
can go from $r^{\prime}$ to $r_{\min}$ – so $(b_{\max},r_{\min})$ becomes part
of the traversal. Again by (ii), while Red is at $r_{\min}$, Blue can go from
$b_{\max}$ to $b^{\prime}$. From $(b^{\prime},r_{\min})$, Blue and Red can
follow $\tau$ to complete the traversal. ∎

Lemma 3 allows us to assume, w.l.o.g., that $b_{\max}$ and $r_{\min}$ are the
first points of $B$ and $R$, respectively (i.e.,
$B[1]=b_{\max},R[1]=r_{\min}$): for arbitrary $B,R$ we can separately solve
the problem for the subpaths of Blue from $b_{\max}$ to $B[n]$ and Red from
$r_{\min}$ to $R[n]$, and the problem for the (reversed) subpaths of Blue from
$b_{\max}$ to $B[1]$ and Red from $r_{\min}$ to $R[1]$.

Figure 1: Determining if $SDW(B,R)>0$: viewing the traversals of the Red and
Blue paths, $R$ and $B$, in space-time.

Let $b_{\min}$ (resp., $r_{\max}$) be the leftmost (resp., rightmost)
$x$-coordinate of $B$ (resp., $R$). If $b_{min}\leq R[1]$, or $r_{max}\geq
B[1]$, then by Lemma 3 (i) we get $FF(B,R)=0$. In addition, if
$b_{\min}>r_{\max}$, then we see that $FF(B,R)>0$, since the $x$-coordinates
of the paths do not overlap. We are thus left with the case in which
$R[1]<b_{\min}\leq r_{\max}<B[1]$ (see Figure 1). If $B[n]>r_{\max}$, then a
feasible traversal has Red remain at $R[1]$ while Blue traverses $B$ from
$B[1]$ to $B[n]$, after which Red can traverse $R$ from $R[1]$ to $R[n]$.
Thus, assume that $B[n]\leq r_{\max}$; this is the case shown in the figure.

Let $B^{+}$ be the last vertex on the Blue path such that $B^{+}>r_{\max}$.
Notice that such a vertex always exists because $B[1]>r_{\max}$. Let $R^{-}$
be the leftmost vertex on the Red path after it visits $r_{\max}$ for the last
time.

######  Lemma 4.

If $FF(R,B)>0$, then there exist a traversal achieving $FF(R,B)>0$ such that
at some point Blue is at $B^{+}$ and Red is at $R^{-}$.

###### Proof.

Consider a traversal $\tau^{\prime}$ where Blue traverses the path from $B[1]$
to $B^{+}$ while Red is at $R[1]$, then Red traverses the path from $R[1]$ to
$R^{-}$ while Blue is at $B^{+}$. Such a traversal is always possible because
$B^{+}$ is to the right of $r_{\max}$. Now consider a traversal $\tau$
achieving $FF(R,B)>0$. We show how to complete $\tau^{\prime}$ to a traversal
achieving $FF(R,B)>0$.

If in $\tau$ Red visits $R^{-}$ before Blue visits $B^{+}$, then let $r_{1}$
be the location of Red when Blue is at $B^{+}$. Since $B^{+}$ is to the right
of $r_{\max}$, in $\tau^{\prime}$ we can have Red traverse the path from
$R^{-}$ to $r_{1}$ while Blue is at $B^{+}$. Then, continue as in $\tau$ to
complete the traversal.

Else, in $\tau$ Blue visits $B^{+}$ before Red visits $R^{-}$. Let $b_{1}$ be
the location of Blue when Red is at $R^{-}$, and let $b_{2}$ be the location
of Blue when Red is at $r_{\max}$ in the traversal $\tau$. In $\tau$, Blue
traverses the subpath from $b_{2}$ to $b_{1}$ while Red traverses the subpath
from $r_{\max}$ to $R^{-}$. Now, since $R^{-}$ is the leftmost point on the
subpath from $r_{\max}$ to $R^{-}$, Blue can traverse the subpath from $b_{2}$
to $b_{1}$ while Red is at $R^{-}$. Notice that $b_{2}$ either precedes
$B^{+}$, or it is on the edge incident to $B^{+}$. Therefore, in
$\tau^{\prime}$ we can have Blue traverse the subpath from $B^{+}$ to $b_{1}$
while Red is at $R^{-}$. Again we continue as in $\tau$ to complete the
traversal. ∎

By the above lemma, we can simply use the following traversal: Blue traverses
$B$ from $B[1]$ to $B^{+}$ while Red is at $R[1]$. Then Red traverses $R$ from
$R[1]$ to $R^{-}$ while Blue is at $B^{+}$. The situation now is: Blue is at
$B^{+}$ and the subpath of Blue starting at $B^{+}$ is entirely to the left of
$B^{+}$ (because $B[n]\leq r_{\max}$); Red is at $R^{-}$ and the subpath of
Red starting at $R^{-}$ is entirely to the right of $R^{-}$. Also note that
$R^{-}$ is not the first vertex of $R$. We are thus back to our initial
conditions, and can apply the algorithm recursively. More formally, consider
the following recursive algorithm. Given two curves $R,B$ such that $R[1]\leq
B[1]$, $r_{\min}=R[1]$ is the leftmost point in $R$ and $b_{\max}=B[1]$ is the
rightmost point in $B$:

  1. 1.

Find $b_{\min}$ and $r_{\max}$.

  2. 2.

If $b_{\min}\leq R[1]$ or $r_{\max}\geq B[1]$, return NO.

  3. 3.

If $b_{\min}>r_{\max}$ or $B[n]>r_{\max}$, return YES.

  4. 4.

Else, find $B^{+}$ and $R^{-}$. Recurse with $B^{+},\dots,B[n]$ and
$R^{-},\dots,R[n]$.

Running time. We begin with a preprocessing step, where we sort the vertices
of $R$ and $B$. For the decision algorithm, given a value $\delta$, we merge
the sorted lists of $R$ and $B-\delta$ in linear time. Then, we can compute in
linear time: (i) The leftmost and rightmost vertices that follow each vertex
of the curve (this can be done in a single scan of the curve). (ii) For each
vertex $r$ of $R$, the last vertex of $B$ that is located to the right of $r$.
In each recursive step of the algorithm, we can compute the points $b_{\min}$,
$r_{\max}$, $B^{+}$, and $R^{-}$, in linear time. Thus, the total running time
for the decision procedure is $O(n)$. For the optimization (finding the
maximum $\delta$ that allows separation), we note that the maximum separation
is achieved when Red and Blue are on vertices, because otherwise, their
distance can increase by having one of them wait on a vertex. Thus, for
finding the maximum possible $\delta$, we can do a binary search among the
$O(n^{2})$ different distances, using distance selection at each step in
$O(n\log n)$ time. The distance selection algorithm stores all $O(n^{2})$
distances implicitly in a sorted matrix, and then applies the sorted matrix
selection algorithm of [FJ84] in $O(n\log n)$ time.

######  Theorem 5.

Given two polygonal curves $P,Q$ of length $n$ in 1D, their social distance
width, $FF(P,Q)$, can be computed in $O(n\log^{2}n)$ time.

###  2.2 Quadratic time algorithms

In this section we describe algorithms for computing continuous and discrete
$FF(R,B)$; the algorithms are based on similar algorithms for computing the
continuous and discrete Fréchet distances, in times $O(n^{2}\log n)$ and
$O(n^{2})$, respectively. As with Fréchet distance, our algorithms use the
notion of a free-space diagram, appropriately adapted.

The free space diagram. The _$\delta$ -free space diagram_ [AG95] of two
curves $P$ and $Q$ represents all possible traversals of $P$ and $Q$ with
Fréchet distance at most $\delta$. We adapt this notion to our new setting.

Let $\mathcal{C}_{ij}=[i,i+1]\times[j,j+1]$ be a unit square in the plane, for
integers $1\leq i\leq n-1$ and $1\leq j\leq m-1$. Let
$\mathcal{B}=[1,n]\times[1,m]$ be the square in the plane that is the union of
the squares $C_{ij}$. Given $\delta>0$, the _$\delta$ -free space_ is
$\mathcal{F}_{\delta}=\\{(p,q)\in\mathcal{B}\mid\|P(p)-Q(q)\|\geq\delta\\}$.
In other words, it is the set of all red-blue positions for which the distance
between the agents is at least $\delta$. A point
$(p,q)\in\mathcal{F}_{\delta}$ is a free point, and the set of non-free points
(or forbidden points) is then $\mathcal{B}\setminus\mathcal{F}_{\delta}$. Note
that for Fréchet distance, these definitions are reversed (“flipped”). We call
the squares $\mathcal{C}_{ij}$ the _cells_ of the free space diagram; each
cell may contain both free and forbidden points. An important property of the
free space diagram is that the set of forbidden points inside a cell
$\mathcal{C}_{ij}$ (i.e., $\mathcal{C}_{ij}\cap\mathcal{F}_{\delta}$) is
convex [AG95].

Figure 2: Right: a free space cell $\mathcal{C}_{ij}$. For FF, the free space
is white, while for Fréchet distance, the free-space is gray. The gray region
within a cell is convex. Left: the free space diagram of two curves. The black
points and dashed lines indicate critical values of type (iii), which are
openings in the free space diagram defined by two red edges and one blue edge.

Notice that a monotone path through the free space $\mathcal{F}_{\delta}$
between two free points $(p,q)$ and $(p^{\prime},q^{\prime})$ corresponds to a
traversal of $P[p,p^{\prime}]$ and $Q[q,q^{\prime}]$. Thus,
$FF(P,Q)\geq\delta$ if and only if there exists a monotone path through the
free space $\mathcal{F}_{\delta}$ between $(0,0)$ and $(n,n)$ (i.e. $(n,n)$ is
“reachable” from $(0,0)$). The Fréchet distance between $P$ and $Q$ can be
computed in $O(n^{2}\log n)$ time [AG95] as follows. For a given value of
$\delta$, the reachability diagram is defined to be the set of points in
$\mathcal{F}_{\delta}$ reachable from $(0,0)$. As the set of free points in
each cell is convex, the set of “reachable” points on each of the boundary
edges of a cell is a line segment. Thus, one can construct in constant time
the reachable boundary points of a cell, given the reachable boundary points
of its bottom and left neighbor cells (see Figure 2). Therefore, computing the
reachability diagram (and hence solving the decision version of the problem)
takes $O(n^{2})$ time using a dynamic programming algorithm. For the
optimization, there are $O(n^{3})$ critical values of $\delta$, which are
defined by (i) the distances between starting points and endpoints of the
curves, (ii) the distances between vertices of one curve and edges of the
other, and (iii) the common distance of two vertices of one curve to the
intersection point of the bisector with some edge of the other. Then,
parametric search, based on sorting, can be performed in time
$O((n^{2}+T_{dec})\log n)$, where $T_{dec}$ is the running time for the
decision algorithm.

In the case of $FF$, we can again compute the reachability diagram in
$O(n^{2})$ time, as in each cell the set of forbidden points is convex, and
thus the set of “reachable” points on each of the boundary edges of a cell is
at most two line segments. The set of critical values is similar, except that
the third type can occur between three edges (see Figure 2, left). Thus, by
arguments similar to [AG95], we have a $O(n^{2}\log n)$ time algorithm for
computing $FF(P,Q)$.

######  Theorem 6.

There is an $O(dn^{2}\log n)$ time exact algorithm for computing the Flipped
Fréchet measure of two polygonal $n$-vertex curves in ${\mathbb{R}}^{d}$.

For the discrete version of $FF$, a simple dynamic programming algorithm
(similar to the one known for discrete Fréchet distance) gives an $O(n^{2})$
solution. In short, let $OPT[i,j]$ be the FF of $P[1,i]$ and $Q[1,j]$; then,
by the definition of $dFF$ we have
$OPT[i,j]=\min\\{\|P[i]-Q[j]\|,\max\\{OPT[i-1,j],OPT[i,j-1],OPT[i-1,j-1]\\}\\}$.

######  Theorem 7.

There exists an $O(dn^{2})$ time exact algorithm for computing the $dFF$
measure of two polygonal $n$-vertex curves in ${\mathbb{R}}^{d}$.

###  2.3 Quadratic lower bounds

Bringmann and Mulzer [BM16] give a lower bound (conditioned on SETH) for
computing the discrete Fréchet distance between two curves in 1D, using a
reduction from the Orthogonal Vectors (OV) problem. We prove similar results
below for FF in 2D and dFF in 1D.

The Orthogonal Vectors problem is defined as follows. Given two sets
$U=\\{u_{1}\ldots u_{N}\\}$ and $V=\\{v_{1}\ldots v_{N}\\}$, each consisting
of $N$ vectors in $\\{0,1\\}^{D}$, decide whether there are $u_{i}\in
U,v_{j}\in V$ orthogonal to each other, i.e., $u_{i}(k)\cdot v_{j}(k)=0$ for
every $k=1,\dots,D$ (where $u_{i}(k)$ denotes the $k$th coordinate of
$u_{i}$). Bringmann and Mulzer [BM16] showed that if OV has an algorithm with
running time $D^{O(1)}\cdot N^{2-{\varepsilon}}$ for some ${\varepsilon}>0$,
then SETH fails.

In the following, by an algorithm with approximation factor $\alpha<1$ we mean
an algorithm that outputs a traversal whose maintained separation distance is
at least $\alpha$ times the FF, given by an optimal traversal.

####  2.3.1 Flipped Fréchet in 2D

We first show that for continuous FF, increasing the dimension from 1D (where
we gave a near-linear-time algorithm) to 2D likely rules out subquadratic
algorithms.

######  Theorem 8.

[FF Lower Bound in 2D] There is no algorithm that computes the FF measure
between two polygonal curves of length $n$ in the plane, up to an
approximation factor at least $\frac{\sqrt{5}}{2\sqrt{2}}$, and runs in time
$O(n^{2-\delta})$ time for any $\delta>0$, unless OV fails.

###### Proof.

Set $\alpha=\frac{\sqrt{5}}{2\sqrt{2}}$. Given an instance $U=\\{u_{1}\ldots
u_{N}\\}$, $V=\\{v_{1}\ldots v_{N}\\}$ of OV, we show how to construct two
curves $R$ and $B$ of length $O(N\cdot D)$ in the plane, such that if $U\times
V$ contains an orthogonal pair then $FF(R,B)\geq 1$, and if $U\times V$ does
not contain an orthogonal pair then $FF(R,B)\leq\alpha$. Therefore, if there
exists an algorithm with running time $O(n^{2-{\varepsilon}})$ for computing
$FF$ of two curves of length $n$ in the plane, then $FF(R,B)$ can be computed
in $O((DN)^{2-{\varepsilon}})$, which means that OV can be decided in
$D^{O(1)}\cdot N^{2-{\varepsilon}}$ time, and SETH fails. Moreover, if $FF$
can be approximated up to a factor of $\alpha$, then again we get that OV can
be decided in $D^{O(1)}\cdot N^{2-{\varepsilon}}$ time, and SETH fails. As in
[BM16], we assume that $D$ is even (otherwise add a 0 coordinate to each
vector).

The construction of $R$ (resp. $B$) is such that for each vector $u_{i}\in U$
(resp. $v_{j}\in V$), we construct a vector gadget curve $A_{i}$ (resp.
$B_{j}$), such that if $u_{i}$ and $v_{j}$ are orthogonal then
$FF(A_{i},B_{j})=1$, and otherwise $FF(A_{i},B_{j})\leq\alpha$. Then, we
connect the vector gadgets into curves $R$ and $B$.

Consider the following set of points (see Figure 3):

  * •

Points on the $x$-axis: $x=(-1.5,0)$, $r=(-0.75,0)$, $r^{\prime}=(-0.5,0)$,
$b=(0.25,0)$, $b^{\prime}=(0.5,0)$

  * •

Points on the $y$-axis: $c^{u}_{0}=-c^{d}_{0}=(0,0.75)$,
$c^{u}_{1}=-c^{d}_{1}=(0,0.25)$, $u=-d=(0,0.5)$

  * •

Octagon points: $p_{1}=-p_{5}=(0.25,0.5)$, $p_{2}=-p_{6}=(0.5,0.25)$,
$p_{3}=-p_{7}=(0.5,-0.25)$, $p_{4}=-p_{8}=(0.25,-0.5)$

  * •

Other points: $s_{1}=(1,0.5)$, $t_{1}=(1,-0.5)$, $s_{2}=(-0.25,-0.25)$,
$t_{2}=(0.25,0.25)$

Notice that all the points are located on a regular grid with side length
$0.25$, and that
$\|s_{1}-t_{2}\|=\|t_{1}-s_{2}\|=\|c^{u}_{1}-p_{4}\|=\|c^{u}_{1}-p_{5}\|=\|c^{d}_{1}-p_{1}\|=\|c^{d}_{1}-p_{8}\|=\|r-c^{u}_{1}\|=\|r-c^{d}_{1}\|=\alpha$.

Figure 3: The curves $R$ and $B$ for the continuous FF lower bound.

For each $u_{i}\in U$, the gadget $A_{i}$ is constructed as follows:

$r^{\prime}\bigcirc_{k=1,\dots,\frac{D}{2}}\left(p_{7}\circ p_{8}\circ u\circ
c^{u}_{u_{i}(2k-1)}\circ u\circ p_{8}\circ p_{7}\circ p_{6}\circ p_{5}\circ
d\circ c^{d}_{u_{i}(2k)}\circ d\circ p_{5}\circ p_{6}\right)\circ
r^{\prime}\leavevmode\nobreak\ .$

Similarly, for $v_{j}\in V$, the gadget $B_{i}$ is constructed as follows:

$b^{\prime}\bigcirc_{k=1,\dots,\frac{D}{2}}\left(p_{3}\circ p_{4}\circ d\circ
c^{d}_{v_{i}(2k-1)}\circ d\circ p_{4}\circ p_{3}\circ p_{2}\circ p_{1}\circ
u\circ c^{u}_{v_{i}(2k)}\circ u\circ p_{1}\circ p_{2}\right)\circ
b^{\prime}\leavevmode\nobreak\ .$

It is easy to see that if $u_{i},v_{j}$ are orthogonal then
$FF(A_{i},B_{j})=1$, because the traversal that uses “antipodal” points
maintains distance 1 between Red and Blue. For the other direction, we claim
that if $FF(A_{i},B_{j})>\alpha$, then $u_{i},v_{j}$ are orthogonal. Now
assume that $u_{i}(1)=1$, so $R$ starts with
$r^{\prime},p_{7},p_{8},u,c^{u}_{1}$. Notice that when Blue traverses the
subcurve $b^{\prime},p_{3},p_{4},d$, Red cannot reach $c^{u}_{1}$. If
$v_{j}(1)=1$, then the next move of Blue is toward $c^{d}_{1}$, and the
distance between the agents becomes at most $\alpha$ (if Red in on $p_{8}$
while Blue is on $c^{d}_{1}$ then their distance is exactly $\alpha$). This
means that $u_{i}(1)=v_{j}(1)=1$ is not possible. Therefore, at least one of
$u_{i}(1),v_{j}(1)$ is $0$. Notice that Blue will visit $d$ for the first time
before Red visits $d$ for the first time. Similarly, Red will visit $u$ for
the first time before Blue visits $u$ for the first time. Moreover, Red cannot
reach $r^{\prime}$ before Blue leaves $d$, and Blue cannot reach $b^{\prime}$
before Red leaves $u$. Thus, the movement of Red and Blue is synchronized in
the sense that when Red is moving from $u$ towards $d$, Blue is moving from
$d$ towards $u$, and vice versa. Hence, by similar (symmetric) arguments, we
get that $u_{i}(k)=v_{j}(k)=1$ is not possible for all $k=2,\dots,D$ as well,
and $u_{i},v_{j}$ are orthogonal.

The gadgets $A_{i}$ and $B_{j}$ are connected into $R$ and $B$ as follows:

$R=x\circ(0,0)\circ s_{2}\bigcirc_{i=1,\dots,N}\left(r\circ A_{i}\right)\circ
r\circ t_{2}\circ(0,0)\circ x\leavevmode\nobreak\ ,\qquad
B=\bigcirc_{j=1,\dots,N}\left(s_{1}\circ b\circ B_{j}\circ b\circ
t_{1}\right)\leavevmode\nobreak\ .$

If $u_{i}\in U,v_{j}\in V$ are orthogonal, then Blue traverses
$\bigcirc_{k=1,\dots,j-1}\left(s_{1}\circ b\circ B_{k}\circ b\circ
t_{1}\right)$ while Red stays at $x$, then Blue moves to $s_{1}$. Now Red
moves from $x$ to $(0,0)$, to $s_{2}$, then traverses
$\bigcirc_{k=1,\dots,i-1}\left(r\circ A_{k}\right)$, and moves to $r$ just
before $A_{i}$. Now Blue moves to $b$ just before $B_{j}$, and they traverse
$A_{i}$ and $B_{j}$ in sync, keeping distance $\geq 1$. Now Red moves to $r$
while Blue moves to $b$, then Blue moves to $t_{1}$. While Blue is on $t_{1}$,
Red traverses $\bigcirc_{k=i+1,\dots,N}\left(r\circ A_{k}\right)\circ
r^{\prime}\circ t_{2}\circ x$. Finally, Blue traverses
$\bigcirc_{k=j+1,\dots,N}\left(s_{1}\circ b\circ B_{k}\circ b\circ
t_{1}\right)$ while Red is on $x$.

For the converse, assume that $FF(R,B)>\alpha$. When Red reaches $(0,0)$ for
the first time, Blue must be on $s_{1}$ or $t_{1}$ (or on the edge between
them). If Blue is on $t_{1}$, then it must move towards $s_{1}$ before Red can
continue to $s_{2}$; moreover, when Red reaches $s_{2}$ Blue can only be
strictly above the $x$-axis either on the edge $(t_{1},s_{1})$ or $(s_{1},b)$.
Thus we can assume that when Red is on $s_{2}$, Blue is on $s_{1}$ immediately
before some vector gadget $B_{j}$. Now consider the first time when Red
reaches $t_{2}$. At this time, Blue can be either near $t_{1}$ (strictly below
the $x$-axis) or near $c^{d}_{0}$. However, if Blue is near $c^{d}_{0}$, it is
not possible for the agents to continue their movement: Blue cannot reach $d$
and Red cannot reach $(0,0)$. Thus we can assume that when Red reaches
$t_{2}$, Blue is near $t_{1}$ and strictly below the $x$ axis. We conclude
that between the first time that Red visited $s_{2}$ and the first time that
Red visited $t_{2}$, Blue had to traverse the vector gadget $B_{j}$ in order
to get from a point strictly above the $x$ axis to a point strictly below it.
Before Blue starts traversing $B_{j}$, it first visits $b$, but when Blue is
on $b$, the only possible location of Red is near $r$ (more precisely, on the
edge between $r$ and $r^{\prime}$, but not on $r^{\prime}$). Notice that Red
cannot be near $x$ since it has not visited $t_{2}$ yet. Now there are two
options: (1) Red is immediately before some vector gadget $A_{i}$, and thus by
previous arguments $u_{i}$ and $v_{j}$ are orthogonal, or (2) Red has finished
all its vector gadgets, and it waits on $r$ while Blue traverses $B_{j}$. In
this case, notice that since $\|r-c_{1}^{u}\|=\|r-c_{1}^{d}\|=\alpha$, Blue
cannot reach any of $c_{1}^{u},c_{1}^{d}$ while Red is on $r$; thus, $v_{j}$
must be a $0$-vector, implying $u_{i}$ and $v_{j}$ are orthogonal. ∎

####  2.3.2 Discrete flipped Fréchet in 1D

######  Theorem 9.

[Discrete 1D Lower Bound] There is no $O(n^{2-{\varepsilon}})$ time
$\alpha$-approximation algorithm for dFF in 1D, for any ${\varepsilon}>0$ and
$\alpha>2/3$, unless OV fails.

###### Proof.

Given an instance $U=\\{u_{1}\ldots u_{N}\\}$, $V=\\{v_{1}\ldots v_{N}\\}$ of
OV, we show how to construct two curves $R$ and $B$ of length $O(N\cdot D)$ on
the line, such that if $U\times V$ contains an orthogonal pair then
$dFF(R,B)\geq 1$, and if $U\times V$ does not contain an orthogonal pair then
$dFF(R,B)\leq 2/3$. Therefore, if there exists an algorithm with running time
$O(n^{2-{\varepsilon}})$ for computing $dFF$ of two curves of length $n$ on
the real line, then $dFF(R,B)$ can be computed in $O((DN)^{2-{\varepsilon}})$,
which means that OV can be decided in $D^{O(1)}\cdot N^{2-{\varepsilon}}$
time, and SETH fails. Moreover, if $dFF$ can be approximated up to a factor of
$2/3$, then again we get that OV can be decided in $D^{O(1)}\cdot
N^{2-{\varepsilon}}$ time, and SETH fails. Again as in [BM16] we assume that
$D$ is even.

Figure 4: For a pair of orthogonal vectors, Red and Blue jump in sync between
$a$s and $b$s, with at least one of them at a "far" point (indexed with 0)

Consider the following set of points on the line (see Figure 4):
$w_{1}=-w_{2}=5/3$, $x_{2}=-x_{1}=1$,
$a^{e}_{0}=b^{o}_{0}=-a^{o}_{0}=-b^{e}_{0}=2/3$,
$a^{e}_{1}=b^{o}_{1}=-a^{0}_{1}=-b^{e}_{1}=1/3$, $s=0$.

We first construct vector gadgets. For each $u_{i}\in U$, we create a
subsequence $A_{i}$ of $R$: for odd (resp. even) $k$, the $k$th point in
$A_{i}$ is $a^{o}_{u_{i}(k)}$ (resp. $a^{e}_{u_{i}(k)}$). Similarly, for
$v_{j}\in V$, we create a subsequence $B_{j}$ of $B$, using $b$s instead of
$a$s. It is easy to see that Red and Blue can traverse $B_{j}$ and $A_{i}$
while maintaining distance 1 if and only if $u_{i},v_{j}$ are orthogonal (they
jump between odd and even points in sync, "opposite" each other, and at least
one of them is at "far" point, indexed with 0). Note that any such vector
gadget has length $D$.

The gadgets $B_{j}$ are connected into $B$ as follows: $B=w_{1}\circ
B_{1}\circ w_{2}\circ w_{1}\circ B_{2}\circ w_{2}\circ\cdots\circ w_{1}\circ
B_{N}\circ w_{2}$. Let $W$ be the sequence of $D(N-1)$ points that alternate
between $a^{o}_{0}$ and $a^{e}_{0}$ starting with $a^{o}_{0}$ (Red can
traverse each of $N-1$ length-$D$ subpaths of $W$ in sync with Blue on any
$B_{j}$). We construct $R$ as follows: $R=W\circ x_{1}\circ s\circ A_{1}\circ
s\circ A_{2}\circ\cdots\circ s\circ A_{N}\circ s\circ x_{2}\circ W$.

The proof that OV is a Yes instance if and only if $dFF(R,B)\geq 1$ is similar
to that in [BM16], with an important change: here, we also show that if OV is
a No instance, then $dFF(R,B)\leq 2/3$. Indeed, notice that since $dFF(R,B)$
is determined by the distance between two vertices, one from $R$ and one from
$B$, we get that if $dFF(R,B)>2/3$, then necessarily $dFF(R,B)\geq 1$ (as
there are no two points in our construction with distance in the range
$(2/3,1)$). Therefore, its is enough to show that if OV is a No instance, then
$dFF(R,B)<1$.

If $u_{i}\in U,v_{j}\in V$ are orthogonal, then Red traverses $D(N-j)$ points
on $W$ while Blue stays at $w_{1}$, then Blue traverses $B_{1}\ldots B_{j-1}$
in sync with Red traversing the rest of $W$. Now, while Blue stays at $w_{1}$
before $B_{j}$, Red goes to $x_{1}$ and traverses $A_{1}\ldots A_{i-1}$, then
goes to $s$ before $A_{i}$. Then, $A_{i},B_{j}$ are traversed in sync, Blue
stays at $w_{2}$ while Red completes the traversal of $A_{i+1},\dots,A_{N}$
and goes to $x_{2}$, and finally Blue can complete the traversal of
$B_{j+1},\dots,B_{N}$ in sync with Red traversing the second $W$ gadget. When
Blue goes to $w_{2}$, Red is able to complete the traversal of $W$.

For the converse, assume that $dFF(R,B)\geq 1$. When Red is on $x_{1}$, Blue
must be to the right of $s$, but if Blue is not on $w_{1}$, then they cannot
take the next step – so Blue must be on $w_{1}$, right before some vector
gadget $B_{j}$. Immediately after leaving $w_{1}$, Blue gets to $b^{o}_{0}$ or
$b^{o}_{1}$, implying that Red must be at $a^{o}_{0}$ or $a^{o}_{1}$, i.e.,
either in some vector gadget $A_{i}$ or on the second $W$ (since it already
passed $x_{1}$). However, if it is on $W$, it must have gone through $x_{2}$
which is too close to $w_{1}$, so Red is in $A_{i}$. Now while they are on
$A_{i}$ and $B_{j}$, Red and Blue must jump in sync, until one of them reaches
the end point of their respective vector gadget. Therefore, if Red did not
start on the first point of $A_{i}$, then it will finish $A_{i}$ and appear at
$s$ before Blue has finished $B_{j}$. This means that $A_{i}$ and $B_{j}$
where traversed simultaneously, and since $dFF(R,B)\geq 1$, the respective
vectors have to be orthogonal. ∎

###  2.4 More than 2 agents

Our algorithm for continuous FF in 1D generalizes to any number $k\geq 2$ of
agents, with a running time of $O(kn\log n)$, as follows. Let
$A_{1},A_{2},\dots,A_{k}$ be the polygonal paths of $k$ agents in 1D. Given a
distance value $\delta$, our goal is to decide whether the $k$ agents can
traverse their respective paths while maintaining distance $\delta$ from one
another. Since we are on a line and agents cannot cross paths, we only need to
maintain distances for neighboring (along the line) agents. Therefore, we can
translate each $A_{i}$ by $-(i-1)\delta$ (for $2\leq i\leq k$), and then our
goal is to find non-crossing traversals, or corresponding paths on the space-
time graph. This can be done by fixing a path for $A_{1}$, then using our
algorithm for two agents to align a corresponding path for $A_{2}$, then
consider the path of $A_{2}$ as fixed, and align a path for $A_{3}$ and so on
(recall that we can have an agent walk in infinite speed).

The question of whether or not there exists an algorithm in 2D with running
time fully polynomial in $k$ remains open (for the Fréchet distance of a set
of curves, the best known running time is roughly $O(n^{k})$; see [DR04]).

##  3 Social distancing in a simple polygon

In this section we consider distancing problems in which the given domain (for
both Red and Blue) is a simple polygon. Since the two agents are moving inside
the same polygon, it is natural to consider geodesic distance (i.e., the
shortest path inside the polygon) instead of Euclidean distance to measure
separation.

Consider a scenario in which Red and Blue have to traverse two polygonal paths
$R$ and $B$, both inside a given polygon $P$, and their goal is to find a
movement strategy (a traversal) that maintains geodesic distance of at least
$\delta$ between them. For the analogous Fréchet problem (Red and Blue have to
maintain geodesic distance of at most $\delta$), Cook and Wenk [CW10]
presented an algorithm that runs in $O(n^{2}\log N)$ time, where $N$ is the
complexity of $P$ and $n$ is the complexity of $R$ and $B$. Their algorithm is
based on the fact that the free space in a cell of the diagram is
$x$-monotone, $y$-monotone, and connected. Then the geodesic decision problem
can be solved by propagating the reachability information through a cell in
constant time, as for the Euclidean Fréchet distance. Thus, we can apply a
similar “flipped” algorithm for computing the $FF(R,B)$ under geodesic
distance in nearly quadratic time.

When both Red and Blue are restricted to traverse a given path, it seems that
the Fréchet-like nature of the problem leads to near-quadratic time
algorithms. Thus, in this section we consider the scenario where Blue has more
freedom, and it is not required to traverse a given path. We first consider
the case when Red is walking on an arbitrary path in the polygon; we show that
while the naive solution takes at least cubic time, there exists a quadratic
time algorithm for this problem. We then describe two variants for which we
present linear time algorithms; the first is where Red is walking along a
shortest path in the polygon, and second is where Red is traversing the
boundary of a skinny polygon (a tree).

Throughout this section, we will use SDW to denote social distancing width, to
differentiate from the Flipped Fréchet versions where both the Red and Blue
curves were given as input.

###  3.1 Red on an arbitrary path mission

Consider the case when Red moves along an arbitrary path $R$ in $P$, and Blue
may wander around in $P$, starting from some given point $b$. The free-space
diagram can be adapted to the case of a path and a polygon, by partitioning
the polygon into a linear number of convex cells (for example, a
triangulation). This is a three-dimensional structure, which contains
$O(n^{2})$ cells (assuming that the complexity of both $R$ and $P$ is $O(n)$).
However, for maintaining geodesic separation, building the free-space may be
cumbersome, because it would involve building the parametric shortest path map
in a triangle as the source moves along a segment, and such SPM may have
$\Omega(n)$ combinatorial changes. Instead, we show that Blue may stay on the
boundary, thus reducing the problem to the standard free-space diagram between
a path and a closed curve. We will prove:

######  Theorem 10.

Let $P$ be a polygon with $n$ vertices, $b$ a point in $P$, and $R$ a path
between two points $r$ and $r^{\prime}$ in $P$. There exists an
$O(n^{2})$-time algorithm to decide whether there exists a path $B$ in $P$
starting from $b$, such that $SDW(R,B)>1$ under geodesic distance.

The proof follows from the following observation and lemma.

######  Observation 11.

Let $p$ be an arbitrary point inside a polygon $P$, and $D$ be the closed
geodesic disk of any radius centered at $p$, then $D$ splits both $P$ and
$\partial P$ into the same number of connected components, and there is a
natural one-to-one correspondence between them.

######  Lemma 12.

Assume that the point $b$ is on the boundary. If there exists a path $B$ in
$P$ starting from $b$, such that $SDW(R,B)>1$ under geodesic distance, then
there exists such a path $B^{\prime}$ that is entirely on the boundary of $P$.

###### Proof.

Let $r_{1}$ be the first point of $R$, and denote by $C_{1},C_{2},\dots,C_{k}$
the set of connected components of $P\setminus D_{r_{1}}$ (where $D_{r_{1}}$
is the unit geodesic disk around $r_{1}$ as in Section 3.2). Assume that $b$
lies in $C_{1}$. When Red moves along $R$, some of the connected components
may disappear, split, or merge with other connected components, and some new
connected components may appear. More formally, we can say that a sequence of
connected components of $P\setminus D_{r}$ (where $r$ is moving continuously
in $P$) belong to the same “combinatorial” connected component, if its
intersection converges to some non-empty area of $P$. By 11, as long as none
of the above changes in the combinatorial definition of $C_{1}$ occur, then
Blue can remain at some point on the boundary of $C_{1}$, because as Red
moves, $C_{1}$ contains a single connected piece of $\partial P$ on which Blue
can walk. Consider the first time when Red reaches a point $r_{2}$ on $R$ such
that $C_{1}$ either disappear, split, or merge. If $C_{1}$ disappears, then
Blue had no way to escape. If $C_{1}$ splits, then by 11, Blue can move on the
boundary of $C_{1}$ to any of the new connected components, right before the
split occurs. If $C_{1}$ merges with another connected component, say $C_{2}$,
then again by 11, Blue can move to the boundary of $C_{2}$ via the boundary of
$C_{1}$. In any of this cases, Blue can move via $\partial P$ to the connected
component in which it was if it would walk along $B$. ∎

Remark. The above lemma applies only to geodesic distance separation - if Blue
is maintaining separation using Euclidean distance, Blue may need to go inside
the polygon (see the figure on the right). In this case we build the 3D free-
space, but note that its complexity is quadratic and it can be searched in
quadratic time.

###  3.2 Red on a shortest path mission

Assume that Red moves along a geodesic path $R$ in $P$ (Red is on a mission
and does not care about social distancing) while Blue may wander around
anywhere within $P$ starting from a given point $b$. We show that the decision
problem, whether Blue can maintain (geodesic) social distance at least 1 from
Red, can be solved in linear time.

######  Theorem 13.

Let $P$ be a polygon with $n$ vertices, $b$ a point in $P$, and $R$ a geodesic
shortest path between two points $r$ and $r^{\prime}$ in $P$. There exists an
$O(n)$-time algorithm to decide whether there exists a path $B$ in $P$
starting from $b$, such that $SDW(R,B)>1$ under geodesic distance.

Figure 5: Left: $D_{r}$ splits $P$ into connected components. Blue escaping
Red as there exists a safe point. Middle: the boundary between $S_{t}$ and
$U_{t}$ is dashed. Blue cannot escape because its connected component equals
$M\setminus D_{r}$. Right: Blue escapes when Red is at $t$.

Proof. We use $|ab|$ to denote the geodesic distance between points $a,b\in
P$. For a point $t\in\mathbb{R}$ let $D_{t}=\\{p\in P:|tp|\leq 1\\}$ be the
unit geodesic disc centered on $t$; let $M=\cup_{t\in R}D_{t}$ be the set of
points within geodesic distance 1 from $R$ (Figure 5, left). Without loss of
generality, assume $b\notin D_{r}$ (otherwise separation fails from the
start). The disk $D_{r}$ splits $P$ into connected components (a component is
a maximal connected subset of $P\setminus D_{r}$): Blue can freely move inside
a component without intersecting $D_{r}$; in particular, if the component
$P^{\prime}\ni b$ of $b$ is not equal to $M\setminus D_{r}$ (i.e., if
$P^{\prime}\setminus M\neq\emptyset$), then Blue can move to a point in
$P^{\prime}\setminus M$ (a safe point) and maintain the social distance of 1
from Red (existence of a safe point can be determined by tracing the boundary
of $M$). Next, we show that the existence of such a safe point is also
_necessary_ for Blue to maintain the distance of 1.

Indeed, as Red follows $R$, $D_{t}$ sweeps $M$; let $S_{t}\subseteq M$ be the
points swept (at least once) by the time Red is at $t\in R$ and let
$U_{t}=M\setminus S_{t}$ be the unswept points. Since $b\notin D_{r}=S_{r}$,
initially Blue is in the unswept region. Assume that there is no safe point
($P^{\prime}=M\setminus D_{r}$) and yet Blue can escape. Suppose Blue can
escape from the unswept to swept when Red is at $t\in R$ (Figure 5, right).
Then there exists a point $p$ on the boundary between $U_{t}$ and $S_{t}$ that
is further than 1 from $t$, say $|pt|=1+{\varepsilon}$ for some
${\varepsilon}>0$. Since $p$ is on the boundary of $S_{t}$, at some position
$t^{*}\in\pi$ before $t$, we had $|t^{*}p|=1$. Since $p$ is on the boundary of
$U_{t}$, there exists an unswept point $p^{\prime}\in U_{t}$ within distance
less than ${\varepsilon}$ from $p$: $|p^{\prime}p|<{\varepsilon}$. Finally,
since $U_{t}=M\setminus S_{t}$ is part of $M$, $p^{\prime}$ becomes swept when
Red is at some point $t^{\prime}\in\pi$ after $t$: $|t^{\prime}p^{\prime}|\leq
1$. We obtain that there are three points $t^{*},t,t^{\prime}$ along a
geodesic path $\pi$ and a point $p$ such that $|t^{*}p|\leq
1<1+{\varepsilon}=|tp|$ and
$|t^{\prime}p|\leq|t^{\prime}p^{\prime}|+|p^{\prime}p|<1+{\varepsilon}=|tp|$,
contradicting the fact that the geodesic distance from a point to a geodesic
path is a convex function of the point on the path [PSR89, Lemma 1] (this is
the place where we use that $R$ is a geodesic path: if $R$ is not geodesic, it
is not necessary for the Blue to escape from $M$ while Red is at $r$).

Figure 6: SPMs from edges and vertices of $\pi$ are computed separately in
parts of $P$ defined by perpendiculars to path edges (some shown dashed). Gray
and lightblue parts are charged to (the right side of) the edge $e$ and to
vertex $u$ of $R$ resp.

We now show how to implement our solution to the decision problem in $O(n)$
time. To build the geodesic unit disk $D_{r}$ we compute the _shortest path
map_ (SPM) from $r$ (the decomposition of $P$ into cells such that for any
point $p$ inside a cell the shortest $r\textrm{-}p$ path has the same vertex
$v$ of $P$ as the last vertex before $p$) – the SPM can be built in linear
time [GH89]; then in every cell of the SPM we determine the points of $D_{r}$:
any cell is either fully inside $D_{r}$, or fully outside, or the boundary of
the disk in the cell is an arc of the radius-($1-|rv|$) circle centered on the
vertex $v$ of $P$. The set $M$ can be constructed similarly, using SPM from
$R$. To build the SPM, we decompose $P$ by drawing perpendiculars to the edges
of $R$ at every vertex of the path (see Figure 6): in any cell of the
decomposition, the map can be built separately because the same _feature_ (a
feature is a vertex or a side of an edge) of $R$ will be closest to points in
the cell (the decomposition is essentially the Voronoi diagram of the
features). In every cell, the SPM from the feature can be built in time
proportional to the complexity of the cell (the linear-time funnel algorithm
for SPM [GH89] works to build the SPM from a segment too: the algorithm
actually propagates shortest path information from segments in the polygon).
Since the total complexity of all cells is linear, the SPM is built in overall
linear time. After $D_{r}$ and $M$ are built, we test whether $b\in D_{r}$ (if
yes, the answer is No) and trace the boundary of $M$ to determine the
existence of a safe point (the answer is Yes iff such a point exists). ∎

###  3.3 SDW of closed curves and polygons

Consider a scenario in which the polygonal curves $R$ and $B$ are closed
curves. Here, the starting points of Red and Blue are not given as an input,
and the goal is to decide whether they can traverse their respective curves
while maintaining distance at least $\delta$. The analogous Fréchet problem
has been investigated by Alt and Godau [AG95], who presented an
$O(n^{2}\log^{2}n)$ time algorithm, and later by Schlesinger et. al. [SVY14],
who improved the running time to $O(n^{2}\log n)$. Those algorithms include
the construction of dynamic data structures for the free space diagram, which
is again based on the fact that the free space within a cell is convex. Since,
in our “flipped” case, the forbidden space is convex, similar data structures
can be used in order to compute the SDW of two closed curves in near quadratic
time.

We can then define the Social Distance Width of two polygons $P_{1},P_{2}$ as
a special case in which $R$ is the boundary of $P_{1}$ and $B$ is the boundary
of $P_{2}$; i.e., $SDW(P_{1},P_{2})=SDW(\partial P_{1},\partial P_{2})$.
Similarly, the Social Distance Width of a (single) polygon $P$ is
$SDW(P)=SDW(\partial P,\partial P)$. We have

######  Theorem 14.

The social distance width of a polygon $P$ of $n$ vertices can be computed
in$O(n^{2})$ time.

The notion of SDW of a polygon is possibly related to other characteristics of
polygons, such as fatness. Intuitively, if the polygon $P$ is fat under
standard definitions, then the SDW of $P$ will be large. However, the exact
connection is yet unclear (see Figure 7), and we leave open the question of
what exactly is the relation between the two definitions.

Figure 7: A $\delta$-fat polygon $P$, and the free space diagram showing that
$SDW(P)\ll\delta$.

We now show that in special cases, the SDW can be computed in linear-time.

###  3.4 Social distancing in a skinny polygon (or a tree)

In this section we consider the case in which the shared domain of Red and
Blue is a tree $T$, and the distance is the shortest-path distance in the tree
(the distance between vertices $u$ and $v$ denoted $|uv|$). Red moves around
$T$ in a depth-first fashion: there is no start and end point, it keeps moving
ad infinitum. In particular, if $T$ is embedded in the plane, the motion is
the limiting case of moving around the boundary of an infinitesimally thin
simple polygon, and the distance is the geodesic distance inside the polygon.

######  Theorem 15.

Let $T$ be a tree with $n$ vertices, embedded in the plane, and $R$ be a
traversal of $T$ in a depth-first fashion. There exists an $O(n)$-time
algorithm to find a path $B$ in $T$ that maximizes $SDW(R,B)$ under the
geodesic distance.

Proof. We start with the case when $T$ is a star (Figure 8, left). Let $r$ be
the root of the star and let $|ra|\geq|rb|\geq|rc|$ be the 3 largest distances
from $r$ to the leaves (i.e., the distance to the root from all other leaves
is at most $|rc|$). Assume that the leaves $a,b,c$ are encountered in this
order as Red moves around $T$ (this assumption is w.l.o.g., since the other
orders are handled similarly); we call $r$ and $|rc|$ the _2-outlier center_
and _radius_ of $T$ because allowing 2 outliers, $|rc|$ is the smallest radius
to cover $T$ with a disk centered at a vertex of the tree. Now, on the one
hand, Blue can maintain distance $|rc|$ from Red: when Red is at $a$, Blue is
at $c$; when Red is at $b$, Blue moves to $a$; when Red is at $c$, Blue moves
to $b$; the minimum distance of $|rc|$ is achieved when Blue is at $c$. On the
other hand, the distance must be at least $|rc|$ at some point, since Blue
cannot sit at $a$ or at $b$ all the time, and, while Blue moves from $a$ to
$b$ through $r$, Red must be somewhere else (other than $a$ or $b$).

Figure 8: Red is at $c$ while Blue moves between $a$ and $b$. Left: A star.
Right: An arbitrary tree.

We now consider an arbitrary tree $T$. Let $r\in T$ be a vertex. Removal of
$r$ disconnects $T$ into several trees; for a vertex $v\neq r$ of $T$ let
$T_{v}\ni v$ be the subtree of $v$. Let $a$ be the vertex of $T$ furthest from
$r$, let $b$ be the vertex of $T\setminus T_{a}$ furthest from $r$, and let
$c$ be the vertex of $T\setminus T_{a}\setminus T_{b}$ furthest from $r$
(Figure 8, right). Call $|rc|$ the _2-outlier radius_ of $r$, and assume
$r^{*}$ is the vertex whose 2-outlier radius is the largest. As in a star,
Blue can maintain the distance of $|r^{*}c|$ from Red by cycling among $a,b,c$
"one step behind" Red. Also as in a star, a larger distance cannot be
maintained because, again, Blue has to pass through $r^{*}$ on its way from
$a$ to $b$, and the best moment to do so is when Red is at $c$.

To find $r^{*}$ in linear time, note that $ab$ is a diameter of $T$: it is a
longest simple path in $T$. All diameters of a tree intersect because if two
diameters $uv,u^{\prime}v^{\prime}$ do not intersect, then there exist
vertices $w\in uv,w^{\prime}\in u^{\prime}v^{\prime}$ that connect the two
diameters and the distance from each of $w,w^{\prime}$ to one of the endpoints
of its diameter is at least half the diameter, implying that the distance
between these endpoints is strictly larger than the diameter (Figure 9, left).
Moreover, since the tree has no cycles, the intersection of all its diameters
is a path $\pi$ in $T$. Notice that the distance from any diameter endpoint to
the closest point on $\pi$ is the same (call it $d$). We claim for any point
$r^{\prime}$ not on $\pi$, the point $r$ on $\pi$ closest to it has a larger
2-outlier radius, and thus $r^{*}$ may be found on $\pi$. Indeed, let $T_{r}$
be the tree that contains $r$ after removing $r^{\prime}$, and let $v$ be the
farthest point from $r^{\prime}$ not in $T_{r}$. Since $|r^{\prime}v|$ is
strictly smaller than the distance between $r$ and the closest diameter
endpoint (See Figure 9, right), we get that the 2-outlier radius of
$r^{\prime}$ is at most $|r^{\prime}v|$. On the other hand, the 2-outlier
radius of $r$ is at least $|rv|$, and clearly $|rv|>|r^{\prime}v|$.

Figure 9: Left: If $|uv|=|u^{\prime}v^{\prime}|=D$, then
$|uww^{\prime}v^{\prime}|>D$. Right: The distance from any diameter endpoint
to the closest endpoint of $\pi$ (thick) is the $d$, for otherwise one of the
diameters is longer than another. The 2-outlier radius of $r$ is $d$, while
the 2-outlier radius of $r^{\prime}$ cannot exceed $d$.

We thus compute a diameter $ab$ (linear time) and pick the vertex with the
largest 2-outlier radius on the diameter as $r^{*}$ by checking the vertices
one by one. As we check consecutive vertices on $ab$, the distances $|ra|$ and
$|rb|$ are updated trivially, and the subtrees $T\setminus T_{a}\setminus
T_{b}$ are pairwise-disjoint for different vertices $r$ along the diameter;
thus the longest paths in all the subtrees can be computed in total linear
time. ∎

The discussion on this special case of thin polygons, leads us to
investigating the more general case of Social Distance Width of two graphs,
which we discuss next.

##  4 Social distancing on graphs

In this section we consider social distancing measures for graphs. We focus on
undirected graphs, but our results readily extend to directed graphs. A
_geometric_ graph is a connected graph with edges that are straight line
segments embedded in the plane. We consider geometric graphs to be
automatically weighted, with Euclidean edge weights.

We will call non-geometric graphs simply as abstract graphs, and unless
otherwise mentioned, we give each edge of an abstract graph a length of one.
Since we are interested in formulating meaningful distance measures, we assume
that an all-pairs shortest path preprocessing has been done on $G$, and
pairwise distances are available in $O(1)$ time. Let $G=(\mathcal{V},E)$,
$n=|\mathcal{V}|$ and $m=|E|$. By a path of length $k$ in an abstract graph
$G=(\mathcal{V},E)$ we mean a sequence $P$ of $k$ vertices:
$P=\\{p_{1},p_{2},\cdots,p_{k}\\}\subseteq\mathcal{V}$, with edges
$p_{i}p_{i+1}\in E$ for all $1\leq i\leq k-1$, and we write $|P|=k$. Note that
we allow vertices to be repeated (that is, we don’t distinguish between a path
and a walk).

For abstract graphs, we assume that Red and Blue both move on the same graph,
as there is no ambient metric defining the distance between Red and Blue. For
geometric graphs, however, we will also consider the case when Red and Blue
move on different graphs or in the embedding space, as the distance between
them is still well-defined.

###  4.1 Abstract Graphs

We state our result for Blue staying away from Red on an abstract graph.

######  Theorem 16 (Blue distancing from Red, abstract).

Assume Red travels on a known path $R$ of length $k$ in an abstract graph $G$,
and Blue can travel anywhere with a speed $s\geq 0$ times that of Red, for
some integer $s$. There exists a decision algorithm for the Blue distancing
from Red-on-a-mission problem that

  * •

for $s\in\\{0,1,n-1\\}$, runs in time $O(km)$,

  * •

for arbitrary $1<s<n-1$, runs in time $O(nk\min(d^{s},n))$, where $d$ is the
maximum degree of any vertex in $G$.

###### Proof.

Take $k$ copies $G_{i}$ of $G$, for $1\leq i\leq k$; let $(v,i)$ be the vertex
corresponding to vertex $v$ in the $i$th copy $G_{i}$. Construct a directed
graph $\tilde{G}$ by connecting these copies as follows (it may be helpful to
imagine these copies “stacked” on top of each other):

  * •

For every $v\in V$ and every $1\leq i\leq k-1$, add a directed edge from
$(v,i)$ to $(v,i+1)$.

  * •

If $s=0$, add no more edges. If $s=1$, add an edge between the vertex $(v,i)$
and vertex $(w,i+1)$ for all neighbors $w$ of $v$ in $G$, for all $(v,i)$,
$1\leq i\leq k-1$.

  * •

If $1<s<n-1$, add an edge between between the vertex $(v,i)$ and vertex
$(w,i+1)$ for all vertices $w$ such that the distance between $w$ and $v$ in
$G$ is at most $s$, for all $(v,i)$, $1\leq i\leq k-1$. Note that there are at
most $d^{s}$ many such vertices, where $d$ is the maximum degree of a vertex
in $G$.

  * •

if $s=n-1$, add an edge from vertex $(v,i)$ to all vertices in $G_{i+1}$.

Let $R=\\{r_{1},r_{2},\cdots,r_{k}\\}$ be the path of Red. Once $\tilde{G}$ is
constructed, delete the vertex $(r_{i},i)$ and all its neighbors from $G_{i}$
if Blue is looking to stay distance at least one away from Red. If Blue
instead aims to stay $\delta$ away, delete the $\delta$ neighborhood of these
vertices from each copy. This results in a graph $G^{\prime}$. If Blue’s
starting position $b$ is given, run BFS/DFS to see if $b$ can reach any vertex
in $G_{k}$, and return yes or no accordingly. If blue can start from any
vertex, then check if any vertex in $G_{1}$ can reach some vertex in $G_{k}$,
and answer yes or no accordingly. The runtime depends on the complexity of
$\tilde{G}$, which is $O(mk)$ if $s\in\\{0,1,n-1\\}$, and $O(nk\min(d^{s},n))$
otherwise, which completes the proof. ∎

###  4.2 Geometric Graphs

Now we consider geometric graphs. Let $R:[0,\ell]\rightarrow\mathbb{R}^{2}$ be
a polygonal curve in $\mathbb{R}^{2}$, consisting of $\ell$ line segments,
with the $i$th line segment $R_{i}=R|_{[i-1,i]}$ where $1\leq i\leq\ell$. We
also assume that each segment $R_{i}$ is parameterized naturally by
$R(i+\lambda)=(1-\lambda)R(i)+\lambda R(i+1)$. The curve $R$ is assumed to be
known: this is how Red is traveling. On the other hand, we are also given a
geometric graph $G$ in which Blue is restricted to travel, and the problem is
to determine if there is a path $P\in G$ (a path in $G$ is the polygonal curve
formed by the edges between the start and end points of $P$), such that
$SDW(R,P)\geq\delta$, where the SDW between $R$ and $P$ is defined as in the
continuous SDW between polygonal curves in Section 2. Note that by adopting
this definition we are considering the Euclidean distance between Red and
Blue: if one instead considers geodesic distance, Red will also need to be
restricted to travel in $G$. We remark on this setting later.

######  Theorem 17 (Blue distancing from Red, geometric).

The decision problem, given $R$ (the path of Red) and $G$ (the graph of Blue),
and a distance $\delta$, can be solved in time $O(km)$, where $k$ is the
length of $R$ (number of vertices) and $m$ is the number of edges in $G$.

###### Proof.

We first define the free space surface for our problem. Consider an edge
$e_{i,j}=(v_{i},v_{j})\in E$, and let $\mathcal{F}_{\delta}^{i,j}$ denote the
$\delta$-free space of $e_{i,j}$ and $R$ (note that
$e_{i,j}:[0,1]\rightarrow\mathbb{R}^{2}$ is a polygonal curve of length 1).
Analogous to [AERW03], we glue the corresponding free-space diagrams of any
two edges in $E$ that share a common vertex, along the boundary of the diagram
that corresponds to this vertex. Doing so for all edges $e_{i,j}\in E$ yields
the free space surface $\mathcal{S}$.

As in [AERW03], we get that there exists a path $P$ in $G$ with
$SDW(R,P)\geq\delta$ if and only if there exists a $y$-monotone path through
the $\delta$-free space in $\mathcal{S}$ between a point $(0,s)$ in some
$\mathcal{F}_{\delta}^{i,j}$, to a point $(k,t)$ in some
$\mathcal{F}_{\delta}^{i^{\prime},j^{\prime}}$. Such a path corresponds to a
continuous surjective traversal of $R$ from $R(0)$ to $R(k)$, and some
continuous non-surjective traversal $P$ of $G$ that starts on a point $s$ on
the edge $e_{i,j}$ and ends on a point $t$ on $e_{i^{\prime},j^{\prime}}$. By
similar arguments, such a path can be found in $O(km)$ time by computing the
reachability diagram as in [AG95].

∎

SDW of a Graph: We now move to defining the social distance width of a graph
that we briefly mentioned above. A curve on a geometric graph corresponding to
a surjective (non-surjective) map will be called a traversal (partial
traversal) of the graph. We note that traversals may need to backtrack, and we
allow partial traversals to do so too.

Define, for two geometric graphs $H$ and $G$,
$SDW(H,G)=\sup_{h,g}\min_{t\in[0,1]}d(h(t),g(t)),$ where $h$ is a traversal of
$H$ and $g$ is a partial traversal of $G$. The setting is that Red is going
about its business on $H$, and must traverse it completely in some order,
while Blue is only trying to stay away, and is restricted to be on $G$.
Finally, we define for a graph $G$, its social distance width, as
$SDW(G)=SDW(G,G)$ where again, we are free to choose either the Euclidean or
the geodesic version.

######  Theorem 18.

For two geometric graphs $H$ and $G$, the Euclidean $SDW(H,G)$ can be computed
in time $O(m_{h}m_{g})$, where $m_{h}$ (resp. $m_{g}$) denotes the number of
edges in the graph $H$ (resp. $G$).

###### Proof.

It is enough to show how to compute $SDW(H,G)$; $SDW(G)$ is then obtained by
putting $H=G$. To this end, we construct the free space surface in a manner
similar to that of the Red-on-a-mission case described previously. For every
edge $e=(u,v)\in H$ and $f=(x,y)\in G$, we construct a free space cell
$C_{e,f}$, which can be thought of as a subset of $[0,1]^{2}$. For edges $e$
and $e^{\prime}$ sharing a vertex $v$, we glue $C_{e,f}$ and
$C_{e^{\prime},f}$ along their right and left edges, respectively, which
correspond to $C_{v,f}$. In this way we obtain a cell complex in three
dimensions, with faces corresponding to cells $C_{e,f}$, edges corresponding
to $C_{u,f}$ (or $C_{v,f}$, $C_{e,x}$, or $C_{e,y}$), and vertices
corresponding to $C_{u,x}$, etc. The rest of the proof follows the lines of
[AERW03]. ∎

The above result shows that when $d$ denotes the Euclidean distance,
$SDW(H,G)$ can be computed in time $O(m_{h}m_{g})$. The following observation
shows that even the geodesic case behaves nicely, as the free space is convex.

######  Lemma 19.

For any $L>0$, the free space (defined to be the points for which the geodesic
distance is at least $L$) inside a cell of the free-space diagram is a convex
polygon.

###### Proof.

Consider 2 edges, $e=(v_{1},v_{2})$ and $f=(u_{1},u_{2})$ in an embedded PSLG
(planar straight line graph), with coordinates $x$ on $e$ such that
$x(v_{1})=0$, $y$ on $f$ such that $y(u_{1})=0$.

Let $d_{1},d_{2},d_{3}$ and $d_{4}$ be the distances between $v_{1}u_{2}$,
$v_{1}u_{1}$, $v_{2}u_{2}$ and $v_{2}u_{1}$, respectively. Then, the geodesic
distance between a point at position $x$ on $e$ and a point at position $y$ on
$f$ is simply

$d(x,y)=\min(x+d_{2}+y,x+d_{1}+|f|-y,|e|-x+d_{4}+y,|e|-x+d_{3}+|f|-y),$

which is a minimum of four functions that are linear in $(x,y)$. Thus,
$d(x,y)$ is concave, piecewise-linear, and the locus of points $(x,y)$ for
which $d(x,y)\geq L$ is a convex polygon, for any $L$.

∎

As a result, we obtain an algorithm with the same running time for geodesic
distance.

## Acknowledgements

We thank the many participants of the Stony Brook CG Group, where discussions
about geometric social distancing problems originated in Spring 2020, as the
COVID-19 crisis expanded worldwide. We would also like to thank Gaurish Telang
for helping to solve a system of non-linear equations.

## References

  * [AERW03] H. Alt, A. Efrat, G. Rote, and C. Wenk.  Matching planar maps.  Journal of algorithms, 49(2):262–283,  2003\.
  * [AG95] H. Alt and M. Godau.  Computing the Fréchet distance between two polygonal curves.  Int. J. Comput. Geom. Appl., 5:75–91,  1995, doi:10.1142/S0218195995000064.
  * [AMP10] E. M. Arkin, J. S. B. Mitchell, and V. Polishchuk.  Maximum thick paths in static and dynamic environments.  Comput. Geom., 43(3):279–294,  2010, doi:10.1016/j.comgeo.2009.02.007.
  * [BF01] C. Baur and S. P. Fekete.  Approximation of geometric dispersion problems.  Algorithmica, 30(3):451–470,  2001, doi:10.1007/s00453-001-0022-x.
  * [BM16] K. Bringmann and W. Mulzer.  Approximability of the discrete Fréchet distance.  JoCG, 7(2):46–76,  2016, doi:10.20382/jocg.v7i2a4.
  * [BOS19] K. Buchin, T. Ophelders, and B. Speckmann.  SETH says: Weak Fréchet distance is faster, but only if it is continuous and in one dimension.  In Proc. of the 30th Annual Symposium on Discrete Algorithms SODA, pages 2887–2901. SIAM,  2019, doi:10.1137/1.9781611975482.179.
  * [Bri14] K. Bringmann.  Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails.  In Proc. of the 55th IEEE Annual Symposium on Foundations of Computer Science FOCS, pages 661–670,  2014, doi:10.1109/FOCS.2014.76.
  * [CHI11] T. H. Chung, G. A. Hollinger, and V. Isler.  Search and pursuit-evasion in mobile robotics - A survey.  Auton. Robots, 31(4):299–316,  2011, doi:10.1007/s10514-011-9241-4.
  * [CW10] A. Cook and C. Wenk.  Geodesic Fréchet distance inside a simple polygon.  ACM Transactions on Algorithms (TALG), 7(1):1–19,  2010\.
  * [DFK+19] E. D. Demaine, S. P. Fekete, P. Keldenich, H. Meijer, and C. Scheffer.  Coordinated motion planning: Reconfiguring a swarm of labeled robots with bounded stretch.  SIAM J. Comput., 48(6):1727–1762,  2019, doi:10.1137/18M1194341.
  * [DR04] A. Dumitrescu and G. Rote.  On the fréchet distance of a set of curves.  In Proceedings of the 16th Canadian Conference on Computational Geometry, CCCG’04, Concordia University, Montréal, Québec, Canada, August 9-11, 2004, pages 162–165,  2004\.
  * [EM94] T. Eiter and H. Mannila.  Computing discrete Fréchet distance.  Technical report, Citeseer,  1994\.
  * [FJ84] G. N. Frederickson and D. B. Johnson.  Generalized selection and ranking: Sorted matrices.  SIAM J. Comput., 13(1):14–30,  1984, doi:10.1137/0213002.
  * [FM04] S. P. Fekete and H. Meijer.  Maximum dispersion and geometric maximum weight cliques.  Algorithmica, 38(3):501–511,  2004, doi:10.1007/s00453-003-1074-x.
  * [GH89] L. J. Guibas and J. Hershberger.  Optimal shortest path queries in a simple polygon.  Journal of Computer and System Sciences, 39(2):126–152,  1989\.
  * [HAB+02] T. Hsiang, E. M. Arkin, M. A. Bender, S. P. Fekete, and J. S. B. Mitchell.  Algorithms for rapidly dispersing robot swarms in unknown environments.  In J. Boissonnat, J. W. Burdick, K. Goldberg, and S. Hutchinson, editors, Algorithmic Foundations of Robotics V, Selected Contributions of the Fifth International Workshop on the Algorithmic Foundations of Robotics, WAFR 2002, Nice, France, December 15-17, 2002, volume 7 of Springer Tracts in Advanced Robotics, pages 77–94. Springer,  2002, doi:10.1007/978-3-540-45058-0\\_6.
  * [HH02] S. Hirsch and D. Halperin.  Hybrid motion planning: Coordinating two discs moving among polygonal obstacles in the plane.  In J. Boissonnat, J. W. Burdick, K. Goldberg, and S. Hutchinson, editors, Algorithmic Foundations of Robotics V, Selected Contributions of the Fifth International Workshop on the Algorithmic Foundations of Robotics, WAFR 2002, Nice, France, December 15-17, 2002, volume 7 of Springer Tracts in Advanced Robotics, pages 239–256. Springer,  2002, doi:10.1007/978-3-540-45058-0\\_15.
  * [OL89] P. A. O’Donnell and T. Lozano-Pérez.  Deadlock-free and collision-free coordination of two robot manipulators.  In Proceedings of the 1989 IEEE International Conference on Robotics and Automation, Scottsdale, Arizona, USA, May 14-19, 1989, pages 484–489. IEEE Computer Society,  1989, doi:10.1109/ROBOT.1989.100033.
  * [PSR89] R. Pollack, M. Sharir, and G. Rote.  Computing the geodesic center of a simple polygon.  Discrete & Computational Geometry, 4(6):611–626,  1989\.
  * [Sch20a] C. Scheffer.  Scheduling three trains is np-complete.  In J. M. Keil and D. Mondal, editors, Proceedings of the 32nd Canadian Conference on Computational Geometry, CCCG 2020, August 5-7, 2020, University of Saskatchewan, Saskatoon, Saskatchewan, Canada, pages 87–93,  2020\.
  * [Sch20b] C. Scheffer.  Train scheduling: Hardness and algorithms.  In M. S. Rahman, K. Sadakane, and W. Sung, editors, WALCOM: Algorithms and Computation - 14th International Conference, WALCOM 2020, Singapore, March 31 - April 2, 2020, Proceedings, volume 12049 of Lecture Notes in Computer Science, pages 342–347. Springer,  2020, doi:10.1007/978-3-030-39881-1\\_30.
  * [SVY14] M. I. Schlesinger, E. Vodolazskiy, and V. Yakovenko.  Similarity of closed polygonal curves in Fréchet metric.  arXiv preprint arXiv:1409.4613,  2014\.