# New Additive Spanner Lower Bounds by an Unlayered Obstacle Product111This
work was supported by NSF:AF 2153680.

Greg Bodwin Gary Hoppenworth University of Michigan University of Michigan
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

For an input graph $G$, an _additive spanner_ is a sparse subgraph $H$ whose
shortest paths match those of $G$ up to small additive error. We prove two new
lower bounds in the area of additive spanners:

  * •

We construct $n$-node graphs $G$ for which any spanner on $O(n)$ edges must
increase a pairwise distance by $+\Omega(n^{1/7})$. This improves on a recent
lower bound of $+\Omega(n^{1/10.5})$ by Lu, Wein, Vassilevska Williams, and Xu
[SODA ’22].

  * •

A classic result by Coppersmith and Elkin [SODA ’05] proves that for any
$n$-node graph $G$ and set of $p=O(n^{1/2})$ demand pairs, one can _exactly_
preserve all pairwise distances among demand pairs using a spanner on $O(n)$
edges. They also provided a lower bound construction, establishing that this
range $p=O(n^{1/2})$ cannot be improved. We strengthen this lower bound by
proving that, for any constant $k$, this range of $p$ is still unimprovable
_even if the spanner is allowed $+k$ additive error among the demand pairs_.
This negatively resolves an open question asked by Coppersmith and Elkin [SODA
’05] and again by Cygan, Grandoni, and Kavitha [STACS ’13] and Abboud and
Bodwin [SODA ’16].

At a technical level, our lower bounds are obtained by an improvement to the
entire _obstacle product_ framework used to compose “inner” and “outer” graphs
into lower bound instances. In particular, we develop a new strategy for
analysis that allows certain _non-layered_ graphs to be used in the product,
and we use this freedom to design better inner and outer graphs that lead to
our new lower bounds.

##  1 Introduction

A basic question arising in robotics [19], circuit design [21, 22, 38],
distributed algorithms [10, 14], and many other areas of computer science (see
survey [5]) is to compress a graph metric $G$ into small space while
approximately preserving its shortest path distances. When this compression is
achieved by a sparse subgraph $H\subseteq G$ whose distance metric is similar
to that of $G$, we call $H$ a _spanner_ of $G$. The setting of spanners on a
linear or near-linear number of edges is considered particularly important in
applications; that is, for an input graph on $n$ nodes, we often want spanners
on $O(n)$ or perhaps $O(n^{1+\varepsilon})$ edges [5].

Spanners were first abstracted by Peleg and Upfal [36] and Peleg and Ullman
[35] after arising implicitly in prior work. Their initial work studied
spanners in the setting of _multiplicative_ error:

######  Definition 1 (Multiplicative Spanners).

For a graph $G$, a subgraph $H\subseteq G$ over the same vertex set is a
$\cdot k$ multiplicative spanner of $G$ if, for all nodes $s,t$, we have
$\texttt{dist}_{H}(s,t)\leq k\cdot\texttt{dist}_{G}(s,t)$.

Optimal bounds for multiplicative spanners were quickly closed in a classic
paper by Althöfer, Das, Dobkin, Joseph, and Soares [9]. For the specific case
of $O(n)$-size spanners, they proved:

######  Theorem 1 ([9]).

Every $n$-node graph has a $\cdot O(\log n)$ multiplicative spanner on $O(n)$
edges. Moreover, there are graphs that do not have an $\cdot o(\log n)$
multiplicative spanner on $O(n)$ edges.

Thus, the question of compression by multiplicative spanners was closed.
However, for many problems, the paradigm of multiplicative error is considered
unacceptable. For example, $\cdot O(\log n)$ multiplicative blowup in travel
time would be unacceptable for a cross-country trucking route. This generated
interest in the community in new error paradigms that perform better on the
_long_ distances in the input graph. Several new types of spanners were
suggested and studied in the following years [25, 39]. The most optimistic was
_purely additive spanners_ , where pairwise distances in the spanner increase
only by an _additive_ error term:

######  Definition 2 (Additive Spanners [32]).

For a graph $G$, a subgraph $H\subseteq G$ over the same vertex set is a $+k$
additive spanner of $G$ if, for all nodes $s,t$, we have
$\texttt{dist}_{H}(s,t)\leq\texttt{dist}_{G}(s,t)+k$.

Unfortunately, high-quality constructions of near-linear-size spanners with
purely additive error remained elusive. That is, the community faced the
following question:

_Do all graphs admit $+k$ additive spanners of near-linear size, with $k$ a
constant, or at least a small enough function of $n$ to be practically
efficient?_

This problem became a central focus of the community following a sequence of
upper bound results. First was the seminal 1995 work of Aingworth, Chekuri,
Indyk, and Motwani [6], which proved that every $n$-node graph has a $+2$
additive spanner on $O(n^{3/2})$ edges. This was followed by a theorem of
Chechik [20] that all graphs have $+4$ spanners on $\widetilde{O}(n^{7/5})$
edges (see also [7]), and from Baswana, Kavitha, Mehlhorn, and Pettie [13] who
proved that all graphs have $+6$ spanners on $O(n^{4/3})$ edges (see also [41,
31]). Thus, it seemed that one might be able to continue this trend, paying
more and more constant additive error in exchange for sparser and sparser
spanners. Unfortunately, a barrier to further progress was discovered by
Abboud and Bodwin [3], who constructed graphs for which any additive spanner
on $O(n^{4/3-c})$ edges suffers $+n^{\Omega(1)}$ additive error. Thus, near-
linear spanners with subpolynomial error are not generally possible.

That said, the lower bound of [3] is a small enough polynomial to be entirely
practical even on enormous input graphs. This work showed graphs for which any
$O(n)$-size spanner pays at least $+n^{1/22}$ error, which is a small enough
polynomial to be entirely practical even on huge input graphs. However, the
upper bounds for $O(n)$-size spanners were far from this ideal. The first
nontrivial constructions of $O(n)$-size spanners [37] (following [18]) had
$+n^{9/16}$ error. Thus began a focused effort by the community to narrow
these upper and lower bounds on additive error towards the middle, with the
goal to determine whether practically-significant constructions of near-linear
additive spanners can be generally achieved.

Despite a high throughput of recent work on the topic, the attainable error
bounds for linear-size additive spanners remain wide open. The initial lower
bound of $+n^{1/22}$ additive error was improved to $+n^{1/11}$ in two
concurrent papers [27, 33], and then recently to $+n^{1/10.5}$ by Lu,
Vassilevska Williams, Wein, and Xu [34] where it stands today. Meanwhile, the
upper bound on additive error was improved to $+\widetilde{O}(n^{1/2})$ [16]
and then to $+n^{3/7+\varepsilon}$ [17] (see also [20, 37]).

###  1.1 New Lower Bounds

The main results of this paper are two new lower bound for additive spanners:

######  Theorem 2 (First Main Result).

There are $n$-node graphs that do not admit a $+o(n^{1/7})$ additive spanner
on $O(n)$ edges.

Our construction follows the _obstacle product framework_ used to prove lower
bounds in prior work, but with a key generalization. Previously, the obstacle
product carefully composes a _layered outer graph_ with a set of _layered
inner graphs_ in a way that causes the shortest paths in the composed graphs
to inherit desirable structural properties from each. We provide a stronger
framework for analysis that allows one to compose _unlayered_ inner and outer
graphs.

It turns out that this unlayering technique also addresses a related open
problem in the area. One can relax additive spanners to _pairwise additive
spanners_ , where we only need to approximate distances among a set of demand
pairs $P$ taken on input:

######  Definition 3 (Pairwise Additive Spanners [23, 24]).

For a graph $G=(V,E)$ and a set of demand pairs $P\subseteq V\times V$, a
subgraph $H\subseteq G$ is a $+k$ additive spanner of $G$ with respect to $P$
if, for all $(s,t)\in P$, we have
$\texttt{dist}_{H}(s,t)\leq\texttt{dist}_{G}(s,t)+k$.

We can then hope for better error bounds in the setting where the number of
demand pairs $|P|$ is not too large. Pairwise spanners were introduced by
Coppersmith and Elkin [23], who specifically focused on the _exact_ $k=0$ case
(also called _distance preservers_); the _approximate_ $k>0$ case has been
studied repeatedly in followup work [1, 28, 29, 30, 31, 24]. The initial paper
by Coppersmith and Elkin [23] established the following fundamental result:

######  Theorem 3 ([23]).

  * •

(Upper Bound) For any $n$-node graph $G=(V,E)$ and set $P\subseteq V\times V$
of $|P|=O(\sqrt{n})$ demand pairs, there is a distance preserver ($+0$
pairwise spanner) on $O(n)$ edges.

  * •

(Lower Bound) For any $p=\omega(\sqrt{n})$, there are $n$-node graphs
$G=(V,E)$ and sets of $|P|=p$ demand pairs that do not admit a distance
preserver on $O(n)$ edges.

Thus, with a budget of $O(n)$ edges, we can exactly preserve distances among
$O(\sqrt{n})$ demand pairs and no more. A question asked repeatedly in
followup work [23, 24, 1] is whether this $\sqrt{n}$ threshold can be improved
if we allow constant $+k$ error; this question was explicitly studied in [24,
1], without resolution. We settle this question negatively:

######  Theorem 4 (Second Main Result).

For any constant $k>0$ and $p=\omega(\sqrt{n})$, there are $n$-node graphs
$G=(V,E)$ and sets of $|P|=p$ demand pairs that do not admit a $+k$ pairwise
spanner on $O(n)$ edges.

On a technical level, this stronger lower bound is again proved using an
unlayered obstacle product. In our view, our new lower bound further cements
the importance of the $\sqrt{n}$ demand pair/$O(n)$ size threshold by
Coppersmith and Elkin: it is even robust to _any constant additive error_.

##  2 Technical Overview of Main Result and Comparison to Prior Work

At a technical level, our main result departs from prior work by altering a
fundamentally different piece of the construction than the one typically
considered previously. We overview the construction and our improvement in the
next section. Here we overview the parts of our construction that match prior
work, and we overview the new technical ingredients that give our improved
lower bounds.

###  2.1 The Obstacle Product Framework

Like every other lower bound in the area, we follow the _obstacle product_
framework. This framework involves composing an _outer graph_ and many copies
of an _inner graph_.

The essential property of the outer graph $G_{O}$ is that it has a set of
_critical pairs_ $P_{O}\subseteq V(G_{O})\times V(G_{O})$, such that:

  * •

for each critical pair $(s,t)$ there is a unique shortest $s\leadsto t$ path
$\pi(s,t)$ in $G_{O}$, called the _canonical path_ , and

  * •

the canonical paths are pairwise edge-disjoint.

If we remove an edge from a canonical path $\pi(s,t)$, then since it is a
unique shortest path, $\texttt{dist}(s,t)$ will increase by at least $+1$. To
amplify this error, we apply an _edge-extension step_ in which we add
$k=n^{\Omega(1)}$ new nodes along every edge. Thus, removing an edge from an
(edge-extended) canonical path $\pi(s,t)$ will cause $\texttt{dist}(s,t)$ to
increase by at least $+k$.

$s$$t$$\pi(s,t)$$\times$$\texttt{dist}(s,t)\geq|\pi(s,t)|+1$$s$$t$$\pi(s,t)$$\times$$\texttt{dist}(s,t)\geq|\pi(s,t)|+k$$\cdots$$\cdots$
Figure 1: Deleting an edge from a canonical path stretches its distance by at
least $+1$. After the _edge extension step_ , deleting an edge stretches
distance by at least $+k$.

Although edge-extension forces any nontrivial spanner of the outer graph to
suffer $+k$ distance error, the problem is that the extended outer graph is
now very sparse: the vast majority of the nodes are new edge-extension nodes
of degree $2$, while only a small handful of nodes are from the original outer
graph and may have higher degree. Thus the trivial spanner, that keeps the
entire outer graph, has $O(n)$ size (where $n$ is the number of nodes after
edge extension) and can be used. The purpose of the next _inner graph
replacement step_ in the obstacle product is to regain this lost density, so
that an $O(n)$-size spanner actually has to remove a significant number of
edges from the graph.

The inner graph $G_{I}$ is equipped with a set of critical pairs $P_{I}$ with
unique edge-disjoint shortest paths, just like the outer graph. We will call
these _inner-canonical paths_ , and the paths in the outer graph _outer-
canonical paths_ to make clear the distinction. Let $v$ be a node in the outer
graph that is contained in exactly $d$ outer-canonical paths, and suppose the
inner graph $G_{I}$ has exactly $|P_{I}|=d$ critical pairs (the case where
these quantities only _approximately_ match, instead of both being exactly
$d$, can be handled easily). We then replace the node $v$ with a copy of the
entire graph $G_{I}$. To preserve outer-canonical paths, we associate each
outer-canonical path $\pi(s,t)$ that intersects $v$ to some inner-canonical
path $\pi(s_{I},t_{I})$ in $G_{I}$. We arrange the composed graph in such a
way that the unique shortest $s\leadsto t$ path in the composed graph is
exactly the original outer-canonical path $\pi(s,t)$, with each node $v$
replaced by the corresponding inner-canonical path $\pi(s_{I},t_{I})$ in the
copy of $G_{I}$ that replaced $v$. We call this unique shortest $s\leadsto t$
path the _composed-canonical path_.

$v$$G_{I}$ Figure 2: To regain lost density from edge extension, the _inner
graph replacement step_ replaces nodes in the outer graph with copies of the
inner graph, carefully attaching canonical paths in the outer graph to
canonical paths in the inner graph.

Most of the edges in the composed graph lie in inner graphs. This implies
that, in any $O(n)$-size spanner $H$ of the composed graph $G_{O}\otimes
G_{I}$, there will be a composed-canonical path $\pi(s,t)$ where the spanner
is missing most of the edges used by $\pi(s,t)$ in inner graphs. We use two
cases to argue that $\texttt{dist}_{H}(s,t)$ must be much longer than
$\texttt{dist}_{G}(s,t)$. In the first case, suppose that the shortest
$s\leadsto t$ path in $H$ uses the same sequence of inner graphs as the
composed-canonical path. It then suffers at least $+1$ error in _most_ of its
inner graphs due to missing edges; it intersects $k=n^{\Omega(1)}$ total inner
graphs, for a total cost of $+\Theta(k)$ additive error. The other case is
when the shortest $s\leadsto t$ path in the spanner avoids these gutted inner
graphs by instead following a path that corresponds to a non-canonical
$s\leadsto t$ path in the outer graph. This other kind of path also suffers
$+\Theta(k)$ error over the composed-canonical path, essentially due to the
edge-extension step.

$s$$t$$\times$$\times$$\times$$+1$$+1$$+1$$k$ inner
graphs$s$$t$$\times$$\times$$\times$$+k$$\cdots$$\cdots$$\times$$\times$$\times$
Figure 3: In any $O(n)$-size spanner $H$, there is a canonical path $\pi(s,t)$
that is missing most of its edges in inner graphs. The additive error of
$s\leadsto t$ paths in the spanner are analyzed in two types: those that
suffer $+1$ error in each inner graph (left), and those that avoid the
problematic inner graphs entirely by following a non-outer-canonical path
(right).

###  2.2 Improvements in Prior Work: Changes to the Alternation Product

Essentially every major improvement in the lower bound has thusfar been
achieved by an improvement to the _alternation product_. Although the
alternation product is not used at all in the technical part of this paper, it
is worth overviewing, to highlight the core difference between the new
improvements in this paper and those obtained in prior work.

The motivating observation behind the alternation product is that, for
correctness of the lower bound, one needs that each edge in an inner graph is
only used by one composed-canonical path. To enforce this, it is actually
_overkill_ to require edge-disjoint outer-canonical paths. Rather, we can
allow the pairwise intersections of outer-canonical paths to contain at most
one edge.

Figure 4: We can allow the outer-canonical paths to contain an edge in their
pairwise intersections (left), and then after the inner graph replacement
step, the composed-canonical paths will become edge-disjoint on inner graphs
(right).

Thus, there is some additional freedom in outer graph design. The alternation
product tries to leverage this freedom for a stronger lower bound. It changes
the edge-disjoint outer-canonical paths into $2$-path-disjoint outer-canonical
paths, in exchange for different relative counts of nodes, critical pairs, and
canonical path lengths in the outer graph. These parameter changes are
favorable when the goal is to build a lower bound _against denser spanners_ ;
for example, the alternation product is necessary to establish the existence
of graphs that need $+n^{\Omega(1)}$ error for any spanner on
$O(n^{4/3-\varepsilon})$ edges. But, in a naive implementation of the
alternation product, these parameter changes are _unfavorable_ when the goal
is lower bounds against $O(n)$-size spanners.

The improved lower bounds of $\Omega(n^{1/11})$ from [27, 33] are mostly
achieved by removing the alternation product from [3] entirely. The subsequent
$\Omega(n^{1/10.5})$ lower bounds of Lu et al [34] reintroduce the alternation
product; their main technical innovation is a clever new implementation of the
alternation product that takes advantage of the geometric structure of the
outer graph to obtain more favorable parameter changes, which make it
beneficial even in the setting of sparse spanners.

###  2.3 Improvements in Our Work: New Inner/Outer Graphs

The current paper obtains achievements in a different way from prior work. We
omit the alternation product entirely; in that sense, our construction forks
[27, 33] rather than [34] (we briefly explain why in the following section).
Rather, we enable a _significant technical change in the design of inner/outer
graphs_ , which we explain next.

Roughly, the goal of the inner/outer graphs is to pack in as many critical
pairs as possible, with as long canonical paths as possible. The main
technical innovation in the $\Omega(n^{1/22})$ lower bound of [3] was to
replace the “butterfly” outer graph implicitly used by Woodruff [40] with a
“distance preserver lower bound graph,” along the lines of a construction by
Coppersmith and Elkin [23] (see also [8, 26] for prior graph constructions
based on a similar technique). Ideally, one would like to use the Coppersmith-
Elkin distance preserver lower bound graphs _exactly_ for inner/outer graphs.
But there’s a catch. When we execute the inner graph replacement step, we need
to make sure that the composed-canonical paths are unique shortest paths in
the composed graph. This property is not immediate, and in fact it does not
hold for arbitrary choices of inner/outer graphs. Rather, it holds if the
inner and outer graphs are both _layered_. But layeredness is not free;
introducing layeredness to the Coppersmith-Elkin construction significantly
harms the inner/outer graph quality, leading to worse lower bounds. All
previous lower bound constructions [40, 3, 33, 27, 34] pay this penalty in
order to layer their graphs.

Lower Bound | Outer Graph | Inner Graph | Alternation Product? | Citation
---|---|---|---|---
$\Omega(\log n)$ | Butterfly | Biclique | No | [40]
$\Omega(n^{1/22})$ | Layered Dist Pres LB | Biclique | Yes | [3]
$\Omega(n^{1/11})$ | Layered Dist Pres LB | Layered Dist Pres LB | No | [27, 33]
$\Omega(n^{1/10.5})$ | Layered Dist Pres LB | Biclique | Improved | [34]
$\Omega(n^{1/7})$ | Dist Pres LB | Dist Pres LB | No | this paper

The technical contribution of our paper can be summarized as follows:

######  Lemma 1 (Main Technical Lemma, Informal).

There are certain amended versions of the Coppersmith-Elkin graphs in [23]
whose structure allows them to be used as inner/outer graphs in the obstacle
product, despite being unlayered.

In addition to its use in spanner lower bounds, this technical lemma is also
the essential missing ingredient towards our extension of pairwise distance
preserver lower bounds of Coppersmith and Elkin to pairwise additive spanners
with $+k$ error (Theorem 4). Our lower bound matches the $\sqrt{n}$ demand
pair threshold obtained by the Coppersmith-Elkin lower bound against distance
preservers precisely because we can use an amended Coppersmith-Elkin distance
preserver lower bound for the outer graph of our obstacle product.

One can view the Coppersmith-Elkin graph construction as parametrized by a
_convex set of vectors_ taken on input. The original graphs in [23] use a
standard convex set construction from [12]. We need to design very precise
convex sets that have essentially the same size as those used by Coppersmith
and Elkin, but with some additional technical properties that enable use with
the obstacle product. Some of our main new technical contributions lie in the
design of these convex sets, which we describe in Section 5.

The other major technical step in this paper lies in the part of the obstacle
product where outer-canonical paths are attached to inner-canonical paths in
the inner graph replacement step. In all prior work, it has been completely
arbitrary which outer-canonical path was attached to which inner-canonical
path. In this work, it is non-arbitrary: we show that the obstacle product
benefits from a specific _alignment_ between these paths; roughly, outer-
canonical paths are attached to inner-canonical paths based on the direction
they are travelling. Details are given in Section 5.3.

With this, we employ a more complex version of the error analysis from prior
work, that leverages our convex set design and alignment between inner and
outer canonical paths. We introduce a _move decomposition framework_ to do so,
which enables an amortized version of the convexity argument used for error
analysis in prior work. A high-level overview of the move decomposition
framework can be found in Section 4, but we will not overview it further here.

###  2.4 Future Directions: Can the Obstacle Product Achieve Tight Error
Bounds?

This research project was initiated by a thought experiment: is it even
_conceivable_ for the obstacle product framework to produce lower bounds
matching the upper bounds obtained by the _path-buying_ framework currently
used for the spanner upper bounds in this paper and in [13, 17]? In this
subsection, we argue that the answer is a resounding “sort of:” on all axes
except one, there is clear potential for these frameworks to produce matching
upper and lower bounds. This problematic axis likely spoils the possibility of
pinning down an exact error bound for $O(n)$-size spanners in the near future,
but this problematic axis is more of a barrier in analysis than in
construction.

Suppose we run the current state-of-the-art upper bound construction from [17]
on lower bound graphs produced by the obstacle product. One arrives at three
main points of technical disagreement, where the upper bound analysis makes
pessimistic assumptions not actually realized on the current lower bound
graph. Thus, a hypothetical tight analysis would have to either introduce a
lower bound graph that realizes these pessimistic assumptions, or it would
need to improve the upper bound argument to avoid making these pessimistic
assumptions in the first place. We overview these points, and their
implications for future work, below.

#### Our Unlayered Inner Graphs Are Probably Necessary.

The path-buying framework used in previous spanner upper bounds [2, 31, 13]
begins with a _clustering_ phase, in which the graph nodes are partitioned
into low-radius “clusters.” In the second _path-buying phase_ , one adds a
collection of shortest paths that connect far-away clusters with small
additive error. A key piece of the upper bound analysis argues that we only
add a small number of shortest paths through each cluster. More specifically,
leveraging distance preserver upper bounds from [23] for a cluster $C$ with
$n_{C}$ nodes, we can afford $O(n_{C}^{1/2})$ shortest paths while paying only
a linear number of edges for this cluster $C$.

When the path-buying framework is run on an obstacle product construction, it
precisely picks out the inner graphs (plus a few nodes in the attached edge-
extended paths) as clusters, and it picks out the outer-canonical paths as the
shortest paths added in the second phase. Thus, for tightness, one would hope
that parameters balance in such a way that we have $\Omega(n_{I}^{1/2})$
canonical paths through each inner graph on $n_{I}$ nodes. Prior to this work,
this was not so: the forced layered structure of the inner graphs meant that
one actually had to place $\Omega(n_{I}^{2/3})$ canonical paths [27] or even
$\Omega(n_{I})$ canonical paths [3, 34] to achieve a lower bound. By
unlayering our inner graphs, we are able to rebalance parameters to have
$\Omega(n_{I}^{1/2})$ canonical paths through each inner graph for the first
time. Thus, this particular axis is no longer a point of disagreement
following our work; we view our main conceptual contribution as demonstrating
tightness between the path buying and obstacle product frameworks in this
regard.

#### An Improved Alternation Product Is Probably Still Needed.

In the clustering phase of the path-buying framework, each cluster is either
“small” or “large,” depending on its number of nodes. The worst-case input
graphs for the spanner upper bounds would have the structure that all clusters
are right on the small/large borderline; it is a good case when all clusters
are significantly above or below this threshold. As mentioned, when one
clusters obstacle product graphs, the clusters are precisely the inner graphs
plus some of their attached edge-extended paths. However, they would
specifically be classified as _large_ clusters in the upper bound, far away
from this borderline. So the upper bound makes a pessimistic assumption of
borderline clusters that is not actually realized in the current lower bound
construction.

Let us engage for a moment in some wishful thinking. Suppose that we could
apply an alternation product on the outer graph, and then replace in inner
graphs with our current density of canonical paths but with the additional
structure $S\times S$ on their demand pairs (such graphs are constructed in
[23]). This would substantially reduce the number of edge-extended paths
attached to each inner graph, and this change would put our inner graphs right
on the small/large borderline when viewed as clusters. Thus, to resolve this
discrepancy between the path buying and obstacle product frameworks, we think
that the alternation product or something similar is very likely to be the
right tool.

There is no intrinsic barrier to applying an alternation product on top of our
unlayering method, but it complicates the already-delicate geometric details
of our argument in a way that we have not resolved. So we wish to emphasize
that the improved alternation product in [34] remains an important technical
idea, and the natural next step for the area is to integrate this alternation
product (or perhaps one with even further-improved parameters) with our
unlayered inner graphs. In this sense, although our lower bounds improve
numerically on [34], we think it is more conceptually correct to consider our
respective constructions as concurrent state-of-the-art that achieve two
different desirable features of the ultimate lower bound construction, which
will need to be unified in future work.

#### Optimal Outer Graphs Will Probably Be Hard To Achieve.

In order to replace in inner graphs of nontrivial size, we need to start the
obstacle product construction with a relatively dense outer graph, that has
$\text{poly}(n)$ canonical paths passing through a typical node. Such an outer
graph would essentially need to be a distance preserver lower bound as in [23]
(perhaps passed through an obstacle product). The trouble is that it is
arguably out of reach of current techniques to determine the optimal quality
of a distance preserver lower bound graph. Distance preserver lower bounds
have close relationships to several long-standing open problems in extremal
combinatorics, like bounds for the triangle removal lemma [15], and it will
probably be difficult to settle the bounds for distance preservers without
also making a breakthrough on these difficult combinatorial problems.

This paper is the first that is able to use state-of-the-art distance
preserver lower bounds for the outer graph. One can explain a substantial part
of the remaining numerical upper/lower bound gap for additive spanners by
acknowledging that the upper bound implicitly uses off-the-shelf distance
preserver upper bounds, and the lower bound uses distance preserver lower
bounds, and these are far apart. Thus: while it is quite reasonable to think
that the obstacle product might produce tight lower bounds _when an optimal
distance preserver lower bound outer graph is plugged in_ , it will likely be
hard to find a concrete graph to plug in.

##  3 Construction Framework

We now present our lower bound construction. We refer back to the technical
overview (Section 2) for intuition, comparison to prior work, and to highlight
the part of this paper that is new. For simplicity of presentation, we will
frequently ignore issues related to non-integrality of expressions that arise
in our analysis; these issues affect our bounds only by lower-order terms.

###  3.1 Base Graph $G_{B}$

We start by describing a template for a _base graph_ $G_{B}$, which is a
generalized version of the lower bound construction for distance preservers by
Coppersmith and Elkin [23] (they use the following construction with a
particular choice of $W$). The outer and inner graphs in our obstacle product
will both be versions of the base graph, instantiated a bit differently. Graph
$G_{B}$ will have parameters $(x,y,r,W)$.

#### Vertices.

The vertices of the base graph are $[1,x]\times[1,y]$, where $x,y$ are
positive integers that are inputs to the construction. We imagine these
vertices as a subset of $\mathbb{Z}^{2}$, i.e., embedded as points in the
Euclidean plane.

#### The Strongly Convex Set $W$.

The edges and critical pairs of the base graph both depend on an additional
input $W$, which is required to be a _strongly convex set_ of vectors in
$\mathbb{Z}^{2}$. We recall the definition:

######  Definition 4 (Strongly Convex Set).

A set of vectors $W$ is strongly convex if the equation
$\vec{v}_{0}=\lambda_{1}\vec{v}_{1}+\cdots+\lambda_{k}\vec{v}_{k}$ has no
nontrivial solutions with all $\vec{v}_{i}\in W$, $k$ any positive integer,
and $\lambda_{i}$ (possibly negative) scalars with $\sum_{i}|\lambda_{i}|\leq
1$. The trivial solutions are when
$\vec{v}_{0}=\vec{v}_{1}=\cdots=\vec{v}_{k}$.

We will write our strongly convex set as $W(r,\psi)$ to mean that (1) the
$x$-coordinate of all vectors is between $r/2$ and $r$, and (2) the angle
between any vector and the horizontal is in the range $[0,\psi]$ radians. For
a technical reason to follow, we further require that the parameter $r$
satisfies $r\leq\frac{x}{4}$.

#### Critical Pairs.

We next define the set of critical pairs $P$ for the base graph. Let $r$ be an
integer parameter of $G_{B}$ and $W(r,\psi)$ be our chosen strongly convex
set. Let $S=[1,r/2]\times[1,y/2]$, and let $T=[x-r,x]\times[1,y]$. The
critical pairs $P$ are a subset of $S\times T$. Specifically: for each $s\in
S$ and each $\vec{v}\in W(r,\psi)$, let $t=s+k\vec{v}$ where $k$ is the
largest positive integer such that $t\in V$, and include $(s,t)\in P$. We
quickly confirm that this node $t$ is well-defined:

######  Lemma 2.

If we choose $\psi$ so that $0\leq\psi\leq\pi/4$ and $\tan\psi\leq yx^{-1}/2$,
then for all $s\in S,\vec{v}\in W(r,\psi)$ there exists a positive integer $k$
with $t:=s+k\vec{v}\in T$.

###### Proof.

Choose $k$ to be the largest integer such that $s_{1}+kv_{1}\leq x$, where
$s_{1},v_{1}$ are the first coordinates of $s,\vec{v}$ respectively. Since
$\|\vec{v}\|\leq r$, this implies $s_{1}+kv_{1}\geq x-r$, and so the first
coordinate of $s+k\vec{v}$ is in the appropriate range $[x-r,x]$.

For the second coordinate: since $s_{2}\geq 1$ and $\tan\psi\geq 0$, we have
$s_{2}+kv_{2}\geq 1$. Additionally, since $s_{2}\leq y/2$ and $\tan\psi\leq
yx^{-1}/2$, we have $s_{2}+kv_{2}\leq y/2+x\cdot yx^{-1}/2\leq y$. Thus the
second coordinate of $s+k\vec{v}$ is in the appropriate range $[1,y]$,
completing the proof that $s+k\vec{v}\in T$. ∎

This lemma imposes a mild constraint on our choice of $\psi$, which will be
satisfied in the instantiation of our inner and outer graphs from this base
graph.

#### Edges and Canonical Paths.

Each critical pair $(s,t)\in P$ is generated using a vector $\vec{v}\in
W(r,\psi)$; we call this the _canonical vector_ of $(s,t)$. We define the
_canonical $(s,t)$-path $\pi_{B}^{s,t}$_ the $(s\leadsto t)$-path containing
exactly the edges of the form $(s+i\vec{v},s+(i+1)\vec{v})$ for integers
$0\leq i<k$. The edges of the graph are exactly those contained in any
canonical path.

$S$$T$$\psi$$\frac{r}{2}$$r$$W(r,\psi)$ Figure 5: For each node $s\in S$, we
use the strongly convex set $W(r,\psi)$ to generate the the nodes $t\in T$ for
which $(s,t)$ is included as a critical pair, in addition to the generation of
the canonical paths connecting these critical pairs.

#### Important Properties of the Base Graph.

This completes the construction of the base graph; we note its important
structural properties before moving on. A version of this lemma appears
frequently in prior work.

######  Lemma 3 (Properties of Base Graph $G_{B}$, similar to lemmas in [4,
27, 34]).

The base graph $G_{B}=(V,E)$ has the following properties:

  1. 1.

$|V|=xy$

  2. 2.

$|P|=\Theta(ry\cdot|W(r,\psi)|)$

  3. 3.

The canonical paths $\pi_{B}^{s,t}$ are pairwise edge-disjoint.

  4. 4.

For all $s,t\in P$, $\left|\pi_{B}^{s,t}\right|=\Theta(\frac{x}{r})$.
Consequently, $|E|=\Theta(xy\cdot|W(r,\psi)|)$.

  5. 5.

Each canonical path $\pi_{B}^{s,t}$ is the unique shortest $(s,t)$-path in
$G_{B}$.

###### Proof.

  1. 1.

The number of vertices is immediate from construction.

  2. 2.

There is exactly one critical pair in $P$ for each combination of a vertex in
$S$ and vector in $W(r,\psi)$. Thus

$|P|=|S|\cdot|W(r,\psi)|=\Theta(ry\cdot|W(r,\psi)|).$

  3. 3.

Each edge $(a,b)\in E$ uniquely identifies a vector $\vec{v}\in W(r,\psi)$.
Since by construction $(a,b)$ lies on a canonical path, we can subtract
$\vec{v}$ from $a$ zero or more times to reach a node in $S$; since the first
coordinate of $v$ is at least $r/2$ and the width of $S$ is $r/2$, there is a
_unique_ node in $S$ that we can reach in this way. Thus $(a,b)$ also uniquely
identifies the first node of its canonical path $s\in S$. Since $s,\vec{v}$
determine a canonical path, $(a,b)$ lies on a unique canonical path.

  4. 4.

Let $\vec{v}$ be the canonical vector of a critical pair $(s,t)$. Notice that

$\left|\pi_{B}^{s,t}\right|=\frac{\|t-s\|}{\left\|\vec{v}\right\|}.$

Since $P\subseteq S\times T$, the first-coordinate displacement
$|t_{1}-s_{1}|$ is at least $x-2r\geq x/2$. Then since $\|\vec{v}\|\leq r$, we
have

$\left|\pi_{B}^{s,t}\right|=\frac{\|t-s\|}{\|\vec{v}\|}\geq\frac{x-2r}{r}\geq\frac{x}{2r}$

where the last inequality is since we require $r\leq x/4$. Since critical
paths are edge-disjoint and every edge lies on a critical path, it follows
that

$|E|=|P|\cdot\Theta\left(\frac{x}{2r}\right)=\Theta(xy\cdot|W(r,\psi)|).$

  5. 5.

Let $\pi_{B}^{s,t}=(s,s+\vec{v},s+2\vec{v},\dots,t)$ be a canonical path,
where $\pi_{B}^{s,t}$ has $k$ edges and so $t-s=k\vec{v}$. Suppose for the
sake of contradiction that there is some other $(s,t)$-path $\pi$ of length
$j\leq k$ in $G_{B}$, and let $\vec{v}_{i}$ be the vector used to create the
$i^{th}$ edge in $\pi$. Then

$k\vec{v}=t-s=\sum_{i=1}^{j}\vec{v}_{i}.$

Since we have assumed that $\pi\neq\pi_{B}^{s,t}$, this violates strong
convexity property of $W(r,\psi)$, completing the contradiction. ∎

###  3.2 Composing the Final Graph $G$

#### Inner Graph and Outer Graph.

We instantiate two different copies of our base graph, which we will call the
inner graph $G_{I}=(V_{I},E_{I})$ and the outer graph $G_{O}=(V_{O},E_{O})$.
We will use subscripts $I$ and $O$ to indicate the inputs used to create
$G_{I},G_{O}$ respectively. That is: the inner graph has dimensions
$x_{I},y_{I}$, strongly convex set $W_{I}(r_{I},\psi_{I})$, critical pairs
$P_{I}$, and canonical paths $\pi_{I}^{s,t}$. The outer graph parameters are
the same with subscript $O$. Since $G_{I},G_{O}$ are both instantiations of
the base graph, they both satisfy Lemma 3.

#### Inner Graph Replacement Step.

The next step in the construction of $G$ is to replace each vertex in $G_{O}$
with a copy of the inner graph $G_{I}$. For each vertex $u$ in $G_{O}$
replaced with a copy $G_{I}^{u}$ of $G_{I}$, we must reconnect every edge
originally incident to $u$ in $G_{O}$ to some vertex in $G_{I}^{u}$. Recall
that the critical pair set $P_{I}$ is a subset of $S_{I}\times T_{I}$. We will
regard the source vertices $S_{I}$ to be the input ports of $G_{I}^{u}$ and
the sink vertices $T_{I}$ to be the output ports of $G_{I}^{u}$. We will
attach every incoming edge of form $(u-\vec{v},u)$ in $G_{O}$ where
$\vec{v}\in W_{O}$ to an input port in $G_{I}^{u}$. Likewise, we will attach
every outgoing edge of form $(u,u+\vec{v})$ in $G_{O}$ to an output port in
$G_{I}^{u}$.

To perform this attachment, we define a bijection $\phi:W_{O}\mapsto P_{I}$
from the vectors in the outer graph’s strongly convex set to the critical
pairs in $P_{I}$. Later in the analysis, we will specify that $\phi$ is non-
arbitrary; for technical reasons we must specifically choose a bijection
satisfying certain properties. But for now we will prove some useful
properties of the construction that hold regardless of which bijection $\phi$
is used. We note that since $\phi$ is a bijection we gain constraints

$|W_{O}|=|P_{I}|=\Theta(r_{I}y_{I}\cdot|W_{I}|).$

If $\vec{v}\in W_{O}$ and $\phi(\vec{v})=(s,t)$, we plug in the incoming edge
$(u-\vec{v},u)$ into input port $s$ in $G_{I}^{u}$, and we plug in the
outgoing edge of form $(u,u+\vec{v})$ originally in $G_{O}$ into output port
$t$ in $G_{I}^{u}$. We repeat this process for all copies of $G_{I}$ and all
vectors $\vec{v}\in W_{O}$. Let $G^{\prime}$ be the graph resulting from this
process.

#### Edge Subdivision Step.

Let $z$ be a new parameter of the construction. To obtain our final graph $G$,
we subdivide every edge of $G^{\prime}$ corresponding to an original edge in
outer graph $G_{O}$ into a path of length $z=|V_{I}|\cdot|P_{I}|^{-1}$, by
adding new nodes along the edge. We refer to the paths in $G$ replacing edges
from $G_{O}$ as subdivided paths.

#### Critical pairs.

We define the critical pairs $P$ associated to the final graph $G$ as follows:

  * •

For each $(s_{O},t_{O})\in P_{O}$, let $G_{I}^{s_{O}}$ and $G_{I}^{t_{O}}$ be
the inner graph copies in $G$ corresponding to vertices $s_{O}$ and $t_{O}$ in
$G_{O}$. Let $\vec{v}_{O}$ be the canonical vector corresponding to critical
pair $(s_{O},t_{O})\in P_{O}$, and let $\phi(\vec{v}_{O})=(s_{I},t_{I})\in
P_{I}$.

  * •

We then add a critical pair to $P$ from the vertex $s_{I}$ in $G_{I}^{s_{O}}$
paired with the vertex $s_{I}$ in $G_{I}^{t_{O}}$.222In principle we could use
$t_{I}$ in place of $s_{I}$ in $G_{I}^{t_{o}}$, but using $s_{I}$ instead
happens to simplify some technical details later on. Denote these vertices in
$G$ as $s$ and $t$, respectively.

  * •

The associated canonical $(s,t)$-path $\pi^{s,t}$ through the final graph $G$
is the one obtained by starting with $\pi_{O}^{s_{O},t_{O}}$ and replacing
each edge with the corresponding subdivided path in $G$ and each node $u$ with
the canonical path $\pi_{I}^{s_{I},t_{I}}$ in the graph $G_{I}^{u}$, except
that we replace the final node $t_{O}$ with the single node $s_{I}$ in
$G_{I}^{t_{O}}$.We define vector $\vec{v}_{O}\in W_{O}$ to be the canonical
vector of $G$ associated with $\pi^{s,t}$.

We summarize the properties of our construction:

######  Lemma 4 (Properties of Final Graph $G$).

Graph $G=(V,E)$ has the following properties:

  1. 1.

$|V|=\Theta\left(|V_{O}\|V_{I}|\right)$

  2. 2.

$|P|=\Theta\left(r_{O}y_{O}\cdot|W_{O}|\right)$

  3. 3.

The canonical paths $\pi^{s,t}$ for $(s,t)\in P$ are pairwise edge-disjoint.

  4. 4.

For all $(s,t)\in P$,
$\left|\pi^{s,t}\right|=\Theta\left(\frac{x_{O}}{r_{O}}\cdot\frac{x_{I}}{r_{I}}\right)$.
Consequently, $|E|=\Omega(|W_{I}||V|)$.

###### Proof.

  1. 1.

The number of vertices in inner graph copies in $G$ is $|V_{O}\|V_{I}|$. Now
we just need to count the vertices in the subdivided paths of $G$. Each inner
graph copy $G_{I}$ in $G$ is incident to at most $2|W_{O}|$ subdivided paths,
each of which has length $z=|V_{I}|\cdot|P_{I}|^{-1}$. Then since
$|P_{I}|=|W_{O}|$ by our bijection $\phi$, the number of vertices in
subdivided paths is at most $|V_{O}|\cdot
2|W_{O}|\cdot|V_{I}\|W_{O}|^{-1}=2|V_{O}\|V_{I}|$.

  2. 2.

The number of demand pairs follows immediately from Lemma 3 and the fact that
$|P|=|P_{O}|$.

  3. 3.

The fact that canonical paths do not share edges along subdivided paths
follows from edge-disjointness of canonical paths in the outer graph (Lemma
3). The fact that canonical paths do not share edges in inner graph copies
follows by noticing that any two canonical paths in $G_{O}$ with the same
canonical vector $\vec{v}\in W_{O}$ are node-disjoint. Thus, any two canonical
paths in $G$ that use the same inner graph $G_{I}^{u}$ have different
canonical vectors, and so they use different canonical subpaths through
$G_{I}^{u}$, as determined by the bijection $\phi$. The claim then follows
from edge-disjointness of canonical paths in $G_{I}$.

  4. 4.

Let $(s,t)\in P$, and let paths $\pi^{s_{O},t_{O}}$ and $\pi^{s_{I},t_{I}}$ be
the canonical paths in $G_{O}$ and $G_{I}$ respectively used to define
$\pi^{s,t}$. By construction we have

$\left|\pi^{s,t}\right|\geq\left|\pi^{s_{O},t_{O}}\right|\left|\pi^{s_{I},t_{I}}\right|.$

Applying Lemma 3 to bound the lengths of canonical paths, we thus have

$\left|\pi^{s,t}\right|=\Theta\left(\frac{x_{O}}{r_{O}}\cdot\frac{x_{I}}{r_{I}}\right).$

Finally, since canonical paths of $G$ are edge-disjoint and $|W_{O}|=|P_{I}|$,
we have

$\displaystyle|E|\geq|P|\cdot\Theta\left(\frac{x_{O}}{r_{O}}\cdot\frac{x_{I}}{r_{I}}\right)=\Omega\left(|W_{I}|\cdot|V|\right).$
∎

##  4 Analysis Framework

Fix a critical pair of vertices $(s,t)\in P$ in our final graph $G$. Let
$\pi^{*}$ denote the canonical path corresponding to critical pair $(s,t)$ in
$G$, and let $\pi$ be any alternate $s\leadsto t$ path. The majority of our
analysis will be dedicated to proving that $\pi$ is much longer than $\pi^{*}$
in the case where $\pi$ takes at least one subdivided path not in $\pi^{*}$;
specifically, we show $|\pi|-|\pi^{*}|=\Omega(r_{O}^{2/3})$ (see Lemma 19).
After proving this lemma, the rest of the analysis follows arguments similar
to prior work [3, 27, 33, 34].

We begin our analysis by decomposing paths in $G$ into subpaths we call moves.
We define a partition of these moves that we call the moveset $\mathcal{M}$.

######  Definition 5 (Moveset $\mathcal{M}$).

Let $\pi$ be a $(u,v)$-path in $G$ from some input port $u\in S_{I}$ in some
inner graph copy $G_{I}^{(1)}$ to some input port $v\in S_{I}$ in some inner
graph copy $G_{I}^{(2)}$. If no internal vertex of $\pi$ is an input port,
then we call $\pi$ a move. We define the following categories of moves in $G$.

  * •

Forward Move. Path $\pi$ is a forward move if it travels from $u$ to some
output port $w\in T_{I}$ in $G_{I}^{(1)}$ and then takes a subdivided path $e$
from $w$ to reach input port $v$ in $G_{I}^{(2)}$.

  * •

Backward Move. Path $\pi$ is a backward move if it takes some subdivided path
$e$ incident to $u$ to reach some output port $w\in T_{I}$ in $G_{I}^{(2)}$
and then travels to input port $v$ in $G_{I}^{(2)}$.

  * •

Zigzag Move. Path $\pi$ is a zigzag move if it takes some subdivided path
$e_{1}$ incident to $u$ to reach some output port $w_{1}\in T_{I}$ in some
inner graph copy $G_{I}^{(3)}$, then travels to some output port $w_{2}\in
T_{I}$ in $G_{I}^{(3)}$, and then takes a subdivided path $e_{2}$ incident to
$w_{2}$ to reach vertex $v$ in $G_{I}^{(2)}$.

  * •

Stationary Move. Path $\pi$ is a stationary move if $G_{I}^{(1)}=G_{I}^{(2)}$,
i.e. if $u$ and $v$ are input ports in the same inner graph copy.

We define the moveset $\mathcal{M}$ to be the collection of these categories
of moves, namely

$\mathcal{M}=\\{\textsc{Forward, Backward, Zigzag, Stationary}\\}.$

forwardbackwardzigzagstationary$u$ Figure 6: The four types of moves from one
input port to another in our move decomposition of paths. All four moves
pictured here use $u$ as their start node, the circles represent different
copies of the inner graph, and the dotted lines between inner graph copies
represent subdivided paths.

Moves will be the basic unit by which we analyze $(s,t)$-paths in $G$. A
useful property of the moveset is the following.

######  Proposition 1.

Every simple $(s,t)$-path $\pi$ can be decomposed into a sequence of pairwise
internally vertex-disjoint moves from the moveset.

###### Proof.

Let $s_{1},s_{2},\dots,s_{k}$ be the list of input ports contained in $\pi$,
listed in their order in $\pi$. Note that $s_{1}=s$ and $s_{k}=t$. Each
subpath $\pi[s_{i},\dots,s_{i+1}]$ will have no input port as an internal
vertex, and therefore will be a move $m_{i}$. This move $m_{i}$ will be
internally vertex-disjoint from all other moves $m_{j}$, where $i\neq j$,
since $\pi$ is a simple path. It is immediate from the construction of $G$
that $\mathcal{M}$ is a partition of the set of moves in $G$. Then move
$m_{i}$ will belong to some category of moves in $\mathcal{M}$. ∎

Note that the canonical $(s,t)$-path $\pi^{*}$ specifically decomposes into a
sequence of forward moves, each of which take a subdivided path corresponding
to the canonical vector of $\pi^{*}$. Our goal is to compare the length of
$\pi^{*}$ to the length of an arbitrary $(s,t)$-path $\pi$. We will accomplish
this by comparing the moves in the move decomposition of the two paths. We now
identify some geometric notions corresponding to moves that will be useful in
our analysis.

Fix a simple $(s,t)$-path $\pi$, and let $m_{1},m_{2},\dots,m_{k}$ be its move
decomposition, where $m_{i}$ is a move from an input port $s_{i}$ in inner
graph copy $G_{I}^{(i)}$ to an input port $s_{i+1}$ in inner graph copy
$G_{I}^{(i+1)}$, and $s_{1}=s$ and $s_{k+1}=t$. If an inner graph copy
$G_{I}^{(i)}$ replaces a vertex $v\in V_{O}$ in $G$, then we will let
$\texttt{coord}(G_{I}^{(i)})$ be the vector in $\mathbb{Z}^{2}$ with the
coordinates of $v$. We now define several geometric notions that will be
essential to our analysis of path $\pi$ in $G$.

######  Definition 6 (Move vector).

The move vector $\vec{m_{i}}$ corresponding to move $m_{i}$ is defined as

$\vec{m_{i}}=\texttt{coord}\left(G_{I}^{(i+1)}\right)-\texttt{coord}\left(G_{I}^{(i)}\right).$

We may think of moves in the move decomposition as vectors in $\mathbb{Z}^{2}$
between vertices in $G_{O}$ (with vertices in $G_{O}$ corresponding to inner
graph copies $G_{I}$ in $G$). Now let $\vec{v}^{*}\in W_{O}$ be the canonical
vector corresponding to canonical $(s,t)$-path $\pi^{*}$. Corresponding to
each move $m_{i}$, we define a move distance $d_{i}$.

######  Definition 7 (Move distance).

The move distance $d_{i}$ corresponding to move vector $\vec{m}_{i}$ is
defined as $d_{i}=\texttt{proj}_{\vec{v}^{*}}\vec{m}_{i}$, that is, the
(possibly negative) scalar projection of the vector $\vec{m}_{i}$ onto
$\vec{v}^{*}$ in the standard Euclidean inner product.

We roughly use $d_{i}$ as a measure of how much closer or farther we get to
$t$ in $G$ when we take move $m_{i}$. Besides the move distance $d_{i}$ of
$m_{i}$, the other salient property is its length (number of edges) in the
final graph, $|m_{i}|$. We will be comparing the moves of a path $\pi$ against
the moves of $\pi^{*}$, all of which have move distance $\|\vec{v}^{*}\|$ and
the same path length. The following quantity will be useful for this purpose.

######  Definition 8 (Unit length of $\pi^{*}$).

We define the unit length $L_{\pi^{*}}$ of $\pi^{*}$ as
$L_{\pi^{*}}:=\frac{|\pi^{*}|}{\|t-s\|}$.

$L_{\pi^{*}}$ is the number of edges in $\pi^{*}$ per unit distance travelled
in $\mathbb{Z}^{2}$. Using this quantity we can directly compare any move
$m_{i}$ to the moves of $\pi^{*}$ via the following quantity.

######  Definition 9 (Move length difference).

$\Delta(m_{i})=|m_{i}|-L_{\pi^{*}}d_{i}$

The move length difference $\Delta(m_{i})$ is the number of additional edges
used by $m_{i}$ to travel distance $d_{i}$ in the direction $\vec{v}^{*}$, as
compared with the same move in $\pi^{*}$.

######  Proposition 2.

$\sum_{i}\Delta(m_{i})=|\pi|-|\pi^{*}|$

###### Proof.

We have:

$\displaystyle\sum_{i}\Delta(m_{i})=\sum_{i}|m_{i}|-L_{\pi^{*}}\sum_{i}d_{i}=|\pi|-\frac{|\pi^{*}|}{\|t-s\|}\cdot\sum_{i}d_{i}=|\pi|-|\pi^{*}|$

The final equality follows from the fact that
$\sum_{i}d_{i}=\sum_{i}\texttt{proj}_{\vec{v}^{*}}\vec{m}_{i}=\texttt{proj}_{\vec{v}^{*}}(t-s)=\|t-s\|$,
since $\pi$ is an $(s,t)$-path and $\vec{v}^{*}$ is the canonical vector of
$(s,t)\in P$. ∎

Proposition 2 gives us a way to compare $|\pi|$ and $|\pi^{*}|$ at the level
of individual moves. If we could show that for all moves $m$, $\Delta(m)\geq
0$, then we would be a lot closer to our current goal of proving a separation
between $|\pi|$ and $|\pi^{*}|$. (Roughly speaking, the inequality
$\Delta(m)\geq 0$ was immediate in prior constructions.) Unfortunately, this
is not generally true in our construction. Because our inner graph is
unlayered, it’s possible that the canonical inner graph path used by $\pi^{*}$
in copies of inner graph $G_{I}$ is much longer than a different path
connecting some input port to some output port in $G_{I}$, which might be used
in an alternate move $m_{i}$. This would result in negative $\Delta(m_{i})$.

We will outline our fix here, although some technical details are pushed to
later in the argument where they are used. We will use an amortized version of
move difference, based on a potential function
$\Phi:S_{I}\mapsto\mathbb{R}_{\geq 0}$ that we call the _inner graph
potential_. Note that the input to $\Phi$ is an input port in the original
inner graph; we will evaluate $\Phi$ on input ports in various inner graph
copies in the final graph, and so if $a,b$ represent the same input port in
two different inner graph copies, we must have $\Phi(a)=\Phi(b)$. We will
specify $\Phi$ in Section 6. With this, we can define an amortized version of
move difference, $\widehat{\Delta}(m_{i})$.

######  Definition 10 (Amortized move difference).

$\widehat{\Delta}(m_{i}):=\Delta(m_{i})-\left(\Phi\left(s_{i+1}\right)-\Phi\left(s_{i}\right)\right)$

The following proposition shows that the amortized move difference still
captures the difference between $|\pi|$ and $|\pi^{*}|$.

######  Proposition 3.

$\sum_{i}\widehat{\Delta}(m_{i})=|\pi|-|\pi^{*}|$

###### Proof.

We have:

$\sum_{i}\widehat{\Delta}(m_{i})=\sum_{i}\Delta(m_{i})-\sum_{i}(\Phi(s_{i+1})-\Phi(s_{i}))=|\pi|-|\pi^{*}|-(\Phi(t)-\Phi(s))=|\pi|-|\pi^{*}|.$

The final equality follows from the fact that $s$ and $t$ have the same
coordinates in their respective inner graph copies as specified in the
definition of $P$. ∎

In Section 6, we will see that $\widehat{\Delta}(m)\geq 0$ for every move $m$.
Then using Proposition 3 and the unique shortest path property of the base
graph $G_{B}$ (see Lemma 3), we will obtain our desired separation between
$|\pi|$ and $|\pi^{*}|$.

##  5 Specifying the Construction

In the following notation, we will let $n_{I}=|V_{I}|$ and $n_{O}=|V_{O}|$. We
also use a parameter $c>0$; roughly one may think of $c$ as a large constant,
and we will assume where convenient that $c$ is _at least_ a large enough
constant. But, we do not hide $f(c)$ factors in our big-O notation unless
explicitly noted with $O_{c}$ notation. Our goal is to argue that for our
final graph $G$ and for any subgraph $H\subseteq G$ with $\leq cn$ edges,
there exists a pair of vertices $u,v\in V(G)$ such that

$d_{H}(u,v)>d_{G}(u,v)+\Omega_{c}\left(n^{1/7}\right).$

This is a rephrasing of the statement that $O(n)$-size spanners generally
require $\Omega(n^{1/7})$ error. We may also assume where convenient that
$n_{I},n_{O}$ are sufficiently large, relative to $c$. We do not make any
effort to optimize the dependence of our lower bound on $c$; to do so would
imply stronger lower bounds against denser spanners, but it introduces
considerable technical complexity that we do not think is worth it. See [17]
for discussion of these optimizations.

###  5.1 Specifying the Inner Graph

We next specify the parameters $x_{I},y_{I},r_{I},W_{I}$ used to construct the
inner graph $G_{I}=(V_{I},E_{I})$. Relative to a choice of $n_{I}$ for the
_total_ number of nodes in the inner graph, we use dimensions

$x_{I}=2^{-1}n_{I}^{1/2}\cdot c^{50}\qquad\text{and}\qquad
y_{I}=2n_{I}^{1/2}\cdot c^{-50}$

and so $x_{I}y_{I}=n_{I}$. We set $r_{I}=c^{102}$; note that by choice of
large enough $n_{I}$ we have $r_{I}\leq x_{I}/4$. We then define $W_{I}$ to be
the set of $c$ vectors

$\left\\{\left(r_{I}-c+i,\sum_{j=i}^{c}j\right)\mid i\in[1,c]\right\\}.$

Strong convexity of $W_{I}$ follows from the fact that the function
$f:\mathbb{Z}\mapsto\mathbb{Z}$ defined as $f(x)=\sum_{j=x}^{c}j$ is positive
and strictly concave on the interval $[1,c]$. We also notice that for all
$\vec{v}\in W_{I}$, the first coordinate of $\vec{v}$ is in the range
$[r_{I}/2,r_{I}]$. Let $\psi_{I}$ be the largest angle between a vector in
$W_{I}$ and the horizontal. Observe that by taking $c$ to be sufficiently
large, we have

$\tan\psi_{I}\leq\left(r_{I}-c\right)^{-1}\cdot\sum_{j=1}^{c}j\leq
2c^{-100}\leq\frac{y_{I}x_{I}^{-1}}{2}.$

Thus this inner graph construction satisfies the premises of the base graph,
and we have proved:

######  Lemma 5 (Inner Graph Strongly Convex Set).

The set $W_{I}(r_{I},\psi_{I})$ has the following properties:

  1. 1.

$|W_{I}|=c$

  2. 2.

For all $\vec{v}=(v_{1},v_{2})\in W_{I}$, $r_{I}/2\leq v_{1}\leq r_{I}$.
Specifically, $W_{I}\subseteq[r_{I}-c,r_{I}]\times[0,c^{2}]$

  3. 3.

$0\leq\tan\psi_{I}\leq 2c^{-100}$.

The next lemma is a key structural property of our inner graph that enables
its analysis in our move decomposition framework. To enable this lemma, we
need to specifically choose $n_{I}$ such that, for each canonical vector
$(v_{1},v_{2})\in W_{I}$, we have $v_{1}\mid(x_{I}-r_{I}/2)$. In particular,
this can be accomplished by defining $\lambda:=\Pi_{i=1}^{c}(r_{I}-c+i)$ and
choosing $n_{I}$ so that $x_{I}\equiv r_{I}/2\mod\lambda$. Since
$\lambda=\Theta_{c}(1)$, there are infinitely many choices of $n_{I}$ that
satisfy this.

######  Proposition 4.

For all $((s_{1},s_{2}),(t_{1},t_{2}))\in P_{I}$, we have
$t_{1}-s_{1}=x_{I}-r_{I}/2$.

###### Proof.

Let $\vec{v}=(v_{1},v_{2})$ be the canonical vector for
$((s_{1},s_{2}),(t_{1},t_{2}))\in P_{I}$. By choice of $n_{I}$ we have that
$v_{1}\mid(x_{I}-r_{I}/2)$. Now let $k=(x_{I}-r_{I}/2)/v_{1}$, and let
$t^{\prime}=(s_{1},s_{2})+k\vec{v}$. Observe that

$t^{\prime}=(s_{1},s_{2})+k\vec{v}=(s_{1}+kv_{1},s_{2}+kv_{2})=\left(s_{1}+x_{I}-r_{I}/2,s_{2}+v_{2}/v_{1}\cdot(x_{I}-r_{I}/2)\right).$

Since $s\in S_{I}$ we have $s_{1}\in[1,r_{I}/2]$, and so $t^{\prime}$ is a
vertex in $[x_{I}-r_{I}/2+1,x_{I}]\times[1,y_{I}]\subseteq T_{I}$. We then
note that $v_{1}\geq r_{I}/2$ by property 2 of Lemma 5. So the first
coordinate of $t^{\prime}+\vec{v}$ is $>s_{1}+x_{I}$, and thus
$t^{\prime}+\vec{v}\not\in T_{I}$. It follows that $t^{\prime}=(t_{1},t_{2})$,
and so $t_{1}=s_{1}+x_{I}-r_{I}/2$ as desired. ∎

Proposition 4 guarantees that all critical pairs $(s,t)\in P_{I}$ have the
same horizontal displacement. Note that this doesn’t imply that the _graph_
distances between critical pairs in $G_{I}$ is the same. Applying Lemma 3 to
our construction, we summarize the following properties of the inner graph:

######  Lemma 6 (Inner Graph Properties).

Inner graph $G_{I}=(V_{I},E_{I})$ has the following properties:

  1. 1.

$|V_{I}|=n_{I}$

  2. 2.

$|E_{I}|=\Theta(c\cdot n_{I})$

  3. 3.

$|P_{I}|=\Theta(c^{53}\cdot n_{I}^{1/2})$

  4. 4.

The canonical paths $\pi_{I}^{s,t}$ for $(s,t)\in P_{I}$ are pairwise edge-
disjoint.

  5. 5.

The canonical path $\pi_{I}^{s,t}$ is the unique shortest $(s,t)$-path in
$G_{I}$ for all $(s,t)\in P_{I}$.

###  5.2 Specifying the Outer Graph

In our specification of the the outer graph $G_{O}$, we will make use of the
existence of dense strongly convex sets of integer vectors in $\mathbb{Z}^{2}$
with certain nice properties. The existence of these sets follows directly
from the work of [12] on the size of the convex hull of integer points inside
a disk of radius $r$; however, we need to tweak the construction slightly to
enforce a few extra convenient properties. Most of the following lemma follows
directly from [12], but for completeness we give a proof in Appendix A.

######  Lemma 7.

For sufficiently large $r$, there exists a strongly convex set $W(r)$ of
integer vectors in $\mathbb{Z}^{2}$ of size $\Theta(r^{2/3})$ such that:

  1. 1.

For all $\vec{v}\in W(r)$, $r-r^{-1/3}\leq\|\vec{v}\|\leq r$.

  2. 2.

If $S$ is a sector with inner angle $\psi$ of the circle of radius $r$
centered at the origin, then there are at most $O(\psi\cdot r^{2/3})$ vectors
in $W(r)\cap S$.

  3. 3.

For all distinct $\vec{u},\vec{v}\in W(r)$,
$\texttt{proj}_{\vec{v}}\vec{u}<\|\vec{v}\|$. (In other words, for all vectors
$\vec{v}\in W(r)$, the vector in $W(r)$ with the largest magnitude scalar
projection in the direction of $\vec{v}$ is $\vec{v}$ itself. This implies
strong convexity, but is in fact a bit stronger.)

###### Proof.

Deferred to Appendix A. ∎

Now we use the convex set $W(r)$ constructed in Lemma 7 as a starting point
for our construction of $W_{O}(r_{O},\psi_{O})$.

#### Strongly convex set $W_{O}(r_{O},\psi_{O})$ for $G_{O}$.

Let $W(r_{O})$ denote the strongly convex set of Lemma 7 with input parameter
$r_{O}$. By Lemma 7, there exists a circular sector with inner angle
$\psi_{1}=c^{-5}$ radians that contains
$\Omega\left(\psi_{1}r_{O}^{2/3}\right)$ vectors from $W(r_{O})$. By choice of
sufficiently large $c$, we may assume $\psi_{1}\leq\pi/4$. We let
$W^{\prime}(r_{O})$ be the set of vectors in $W(r_{O})$ with endpoints in this
sector.

We will take parameter $\psi_{O}=\pi/4$, i.e. we will modify
$W^{\prime}(r_{O})$ so that its vectors lie in the first quadrant and have
angle at most $\psi_{O}$ with the horizontal. Note that if we reflect the
vectors of $W(r_{O})$ across the lines $x=0$, $y=0$, $y=x$, or $y=-x$ in
$\mathbb{R}^{2}$, then the resulting set of vectors $W^{\prime}(r_{O})$ also
satisfies the properties of Lemma 7. By performing these reflection operations
a constant number of times, we can ensure that at least half the vectors in
$W^{\prime}(r_{O})$ lie in the first quadrant and have angle at most
$\psi_{O}$ with the horizontal. We let $W^{\prime\prime}(r_{O})$ denote the
resulting set of vectors with maximum angle $\psi_{O}$ to the horizontal; we
thus have $|W^{\prime\prime}(r_{O})|=\Omega(c^{-5}r_{O}^{2/3})$.

We are now ready to construct our strongly convex set $W_{O}$ from
$W^{\prime\prime}(r_{O})$. Our set $W_{O}$ will be partitioned into $c$
disjoint sets $\mathcal{S}_{1},\mathcal{S}_{2},\dots,\mathcal{S}_{c}$ called
stripes, which have the following two properties:

  * •

(Same Size) All stripes contain the same number of vectors
$|\mathcal{S}_{i}|=:\beta=\Theta(c^{-6}r_{O}^{2/3})$ vectors.

  * •

(Well-Separated) For any two distinct stripes
$\mathcal{S}_{i},\mathcal{S}_{j}$ and for vectors
$\vec{u}\in\mathcal{S}_{i},\vec{v}\in\mathcal{S}_{j}$, the angle between
$\vec{u},\vec{v}$ is at least $c^{-10}$.

We construct our stripes as follows. Starting at the horizontal and rotating
counterclockwise, let
$\vec{u}_{1}^{1},\vec{u}_{2}^{1},\dots,\vec{u}_{\beta}^{1}$ be the first
$\beta$ vectors we encounter in $W^{\prime\prime}(r_{O})$. After encountering
the $\beta$th vector, we rotate $c^{-10}$ radians about the origin
counterclockwise, ignoring any vectors encountered in this arc. By Lemma 7,
this will skip over only $O(c^{-10}r_{O}^{2/3})$ vectors in
$W^{\prime\prime}(r_{O})$. We then take the next $\beta$ vectors we encounter
to be $\vec{u}_{1}^{2},\vec{u}_{2}^{2},\dots,\vec{u}_{\beta}^{2}$, and again
rotate $c^{-10}$ radians counterclockwise. We repeat this process until we’ve
obtained vectors $\vec{u}_{i}^{j}$ for $i\in[1,\beta]$ and $j\in[1,c]$. We
call the set of of vectors $\\{\vec{u}_{i}^{j}\mid i\in[1,\beta]\\}$ the $j$th
stripe $\mathcal{S}_{j}$ of $W_{O}$. Our procedure is guaranteed to identify
all $c\beta$ vectors $\vec{u}_{i}^{j}$, since we skip over only
$O(c^{-9}r_{O}^{2/3})$ vectors from $W^{\prime\prime}(r_{O})$ in our
construction. Note that $|W_{O}|=c\beta=\Theta(r_{O}^{2/3}c^{-5})$. We
summarize our properties:

######  Lemma 8 (Outer Graph Strongly Convex Set).

For sufficiently large parameters $c,r_{O}$ we may construct a strongly convex
set $W_{O}=W_{O}(r_{O},\psi_{O})$ containing $\Theta(r_{O}^{2/3}c^{-5})$
integer vectors in $\mathbb{Z}^{2}$ with the following properties:

  1. 1.

For all $\vec{v}\in W_{O}$, $r_{O}-r_{O}^{-1/3}\leq\|\vec{v}\|\leq r_{O}$.

  2. 2.

For all $\vec{u},\vec{v}\in W_{O}$,
$\texttt{proj}_{\vec{v}}\vec{u}\leq\|\vec{v}\|$.

  3. 3.

For all $\vec{v}\in W_{O}$, the angle between vector $\vec{v}$ and the
horizontal is at most $\psi_{O}=\pi/4$ radians.

  4. 4.

For all $\vec{u},\vec{v}\in W_{O}$, the angle between $\vec{u}$ and $\vec{v}$
is at most $\psi_{1}=c^{-5}$ radians.

  5. 5.

$W_{O}$ can be partitioned into $c$ stripes
$\mathcal{S}_{1},\mathcal{S}_{2},\dots,\mathcal{S}_{c}$ with the following
properties:

    1. (a)

$|\mathcal{S}_{i}|=\beta=\Theta(r_{O}^{2/3}c^{-6})$ for all $i\in[1,c]$.

    2. (b)

For $\vec{u}\in\mathcal{S}_{i}$ and $\vec{v}\in\mathcal{S}_{j}$ where $i\neq
j$, the angle between $\vec{u}$ and $\vec{v}$ is at least $\psi_{2}=c^{-10}$
radians.

Figure 7: A depiction of $W_{O}$. The endpoints of the vectors in $W_{O}$ lie
in the black stripes in the above figure.

#### Parameter choices for $G_{O}$.

We will let $2x_{O}=y_{O}=\sqrt{2}n_{O}^{1/2}$. We will leave $r_{O}$
unspecified until the end of the construction, for expository purposes, as it
is selected according to a parameter balance on the final graph. However,
unlike with $r_{I}$ in $G_{I}$, our choice of $r_{O}$ will grow polynomially
with $n_{O}$. We quickly verify that our choices satisfy the base graph
construction. We have $\tan\psi_{O}=1=y_{O}x_{O}^{-1}/2$. Additionally, for
all $\vec{v}\in W_{O}$, the first coordinate $v_{1}$ of $\vec{v}$ is between
$r_{O}/2$ and $r_{O}$, by properties 1 and 3 of Lemma 8. Then assuming we
choose $r_{O}\leq n_{O}^{1/2}/4$, it’s clear that our parameter choice
$(x_{O},y_{O},r_{O},W_{O})$ of $G_{O}$ will yield a valid instantiation of
base graph $G_{B}$. The following lemma summarizes the properties of $G_{O}$,
using Lemma 3:

######  Lemma 9 (Outer Graph Properties).

Outer graph $G_{O}=(V_{O},E_{O})$ has the following properties:

  1. 1.

$|V_{O}|=n_{O}$

  2. 2.

$|E_{O}|=\Theta(c^{-5}\cdot r_{O}^{2/3}\cdot n_{O})$

  3. 3.

$|P_{O}|=\Theta(c^{-5}\cdot r_{O}^{5/3}\cdot n_{O}^{1/2})$

  4. 4.

The canonical paths $\pi_{O}^{s,t}$ for $(s,t)\in P_{O}$ are pairwise edge-
disjoint.

  5. 5.

The canonical path $\pi_{O}^{s,t}$ is the unique shortest $(s,t)$-path in
$G_{O}$ for all $(s,t)\in P_{O}$.

###  5.3 Specifying the Final Graph

In our construction of final graph $G$, we made use of a bijection
$\phi:W_{O}\mapsto P_{I}$ to plug the subdivided paths of $G_{O}$ into the
input and output ports of the inner graph copies of $G_{I}$. To that end, we
required that $|W_{O}|=|P_{I}|$. This can be achieved by taking
$n_{I}=\Theta(r_{O}^{4/3}c^{-116})$, so our inner graph will be fully
specified by parameters $c,r_{O}$. Note that we can get exact equality in the
cardinality of $W_{O}$ and $P_{I}$ by simply ignoring a constant fraction of
vectors in $W_{O}$ or a constant fraction of paths in $P_{I}$.

We specifically define $\phi$ as follows. Let
$\vec{v}_{1},\vec{v}_{2},\dots,\vec{v}_{c}$ be the $c$ vectors in $W_{I}$.
Observe that for every $\vec{v}_{i}\in W_{I}$, each vertex $s\in S_{I}$ has a
critical pair in $P_{I}$ with $\vec{v}_{i}$ as its canonical vector. Then
there will be exactly $|P_{I}|c^{-1}$ critical pairs in $P_{I}$ with canonical
vector $\vec{v}_{i}$. Let $\phi$ map the $|W_{O}|c^{-1}$ vectors in stripe
$\mathcal{S}_{i}$ of $W_{O}$ to the $|P_{I}|c^{-1}$ critical pairs in $P_{I}$
with canonical vector $\vec{v}_{i}$, with some arbitrary bijection, for all
$i\in[1,c]$. The following proposition captures the key property of $\phi$
needed in our construction.

######  Proposition 5.

For all $\vec{u},\vec{v}\in W_{O}$, the critical pairs
$\phi(\vec{u}),\phi(\vec{v})\in P_{I}$ have the same canonical inner graph
vector in $W_{I}$ if and only if $\vec{u}$ and $\vec{v}$ belong to the same
stripe $\mathcal{S}_{i}$, $i\in[1,c]$.

For analysis purposes, it will be convenient if the set of canonical paths for
pairs in $P$ partition the edges $E$ of $G$. Currently, the canonical paths
partition the _outer_ extended edges of $G$, since in our base graph
construction we only include edges that lie in canonical paths. However, it
might be that some _inner_ graphs edges $e$ are not used in canonical paths
for pairs in $P$. Specifically, this happens in the case where the inner-
canonical path containing $e$ bijects with a canonical vector $\vec{v}$ that,
in turn, does not define an edge contained in an outer canonical path
(typically because the point corresponding to the inner graph that contains
$e$, plus the vector $\vec{v}$, yields a point outside the $[1,x]\times[1,y]$
dimensions of the outer graph).

To simplify the following analysis we remove all edges in $E$ from inner
graphs that do not belong to a canonical path $\pi^{s,t}$ where $(s,t)\in P$.
Then by properties 3 and 4 of Lemma 4, the canonical paths for pairs in $P$
will partition $E$ and the density of $G$ will remain the same (within
constant factors). We summarize the properties of our final graph:

######  Lemma 10 (Properties of Final Graph $G$).

Graph $G=(V,E)$ has the following properties:

  1. 1.

$|V|=\Theta(r_{O}^{4/3}\cdot c^{-116}\cdot n_{O})$

  2. 2.

$|E|=\sum_{(s,t)\in P}|\pi^{s,t}|=\Theta(c\cdot|V|)$

  3. 3.

$|P|=\Theta(r_{O}^{5/3}\cdot c^{-5}\cdot n_{O}^{1/2})$

  4. 4.

The subdivided paths of $G$ are of length
$z=|V_{I}||P_{I}|^{-1}=\Theta(r_{O}^{2/3}c^{-111})$.

  5. 5.

The set of canonical paths $\\{\pi^{s,t}\mid(s,t)\in P\\}$ form a partition of
$E$.

##  6 Completing the Analysis

As in Section 4, fix a critical pair of vertices $(s,t)\in P$ in our final
graph $G$ with canonical path $\pi^{*}$ and canonical vector $\vec{v}^{*}$. We
will compare $\pi^{*}$ to an arbitrary simple $(s,t)$-path $\pi$, with move
decomposition $m_{1},m_{2},\dots,m_{k}$. As before, move $m_{i}$ is a move
from an input port $s_{i}$ in inner graph copy $G_{I}^{(i)}$ to an input port
$s_{i+1}$ in inner graph copy $G_{I}^{(i+1)}$, and $s_{1}=s$ and $s_{k+1}=t$.

The majority of the analysis in this section will be towards giving lower
bounds for the amortized move difference $\widehat{\Delta}(m_{i})$ of moves
$m_{i}$. Intuitively, we should think of proving lower bounds on
$\widehat{\Delta}(m_{i})$ as proving that move $m_{i}$ is longer than a move
in the canonical path in some sense. In this section, it will be helpful to
recall that $r_{I}=c^{102}$, $x_{I}=2^{-1}n_{I}^{1/2}c^{50}$,
$z=\Theta(n_{I}^{1/2}c^{-53})$, and $n_{I}=\Theta(r_{O}^{4/3}c^{-116})$.

###  6.1 Lower Bounding the Move Difference $\Delta$

We begin our analysis by lower bounding the move difference $\Delta$ of
several categories of moves in the moveset. We will need the following useful
proposition.

######  Proposition 6 (Inner Graph Path Lengths).

  1. 1.

For every $(s_{I},t_{I})$-path $\pi_{I}$ in $G_{I}$, where $s_{I}\in S_{I}$
and $t_{I}\in T_{I}$,

$\frac{n_{I}^{1/2}}{2c^{52}}-2\leq|\pi_{I}|$

  2. 2.

For every critical pair $(s_{I},t_{I})\in P_{I}$ with canonical path
$\pi_{I}^{s_{I},t_{I}}$,

$|\pi_{I}^{s_{I},t_{I}}|\leq\frac{n_{I}^{1/2}c^{50}}{2(c^{102}-c)}$

###### Proof.

  1. 1.

Observe that by the construction of $G_{I}$, the $x$-displacement between any
vertex in $S_{I}$ and any vertex in $T_{I}$ is at least
$x_{I}-2r_{I}=2^{-1}n_{I}^{1/2}c^{50}-2c^{102}$. Additionally, each edge $e\in
E_{I}$ corresponds to a vector $\vec{w}=(w_{1},w_{2})\in W_{I}$, and by
property 2 of Lemma 5, $w_{1}\leq r_{I}=c^{102}$. Then for every $s\in S_{I}$
and $t\in T_{I}$, every $(s_{I},t_{I})$-path in $G_{I}$ is of length at least

$\frac{2^{-1}n_{I}^{1/2}c^{50}-2c^{102}}{c^{102}}=\frac{n_{I}^{1/2}}{2c^{52}}-2$

  2. 2.

The $x$-displacement between any vertex in $S_{I}$ and any vertex in $T_{I}$
is less than $x_{I}=2^{-1}n_{I}^{1/2}c^{50}$. Let
$\vec{v}_{I}^{*}=(v_{I,1}^{*},v_{I,2}^{*})$ be the canonical vector in $W_{I}$
corresponding to $\pi_{I}^{s_{I},t_{I}}$, and note that by property 2 of Lemma
5, $v_{I,1}^{*}\geq r_{I}-c=c^{102}-c$. Then $|\pi_{I}^{s_{I},t_{I}}|$ is a
most $(2^{-1}n_{I}^{1/2}c^{50})/(c^{102}-c)$ as desired.

∎

Now we will lower bound the move length difference $\Delta(m_{i})$ of moves in
Backward. This lemma essentially formalizes the obvious reason why backwards
moves are much worse than canonical moves – it’s because they move backwards,
away from $t$.

######  Lemma 11.

Let $m_{i}$ be a move in Backward. Then
$\Delta(m_{i})=\Omega(r_{O}^{2/3}c^{-110})$.

###### Proof.

Observe that in a backward move, we take a subdivided path corresponding to
some vector $\vec{m}_{i}=-\vec{u}$ for some $\vec{u}\in W_{O}$. Since all
vectors in $W_{O}$ lie in a sector with inner angle $c^{-5}$ by property 3 of
Lemma 8, it follows that the angle between $\vec{u}$ and $\vec{v}^{*}$ is less
than $c^{-5}$, so the angle between $\vec{m}_{i}=-\vec{u}$ and $\vec{v}^{*}$
is at least $\pi-c^{-5}$. Then for sufficiently large $c,r_{O}$, the scalar
projection of $\vec{m}_{i}$ onto $\vec{v}^{*}$ will be negative, so $d_{i}<0$.
Recall that $L_{\pi^{*}}$ is the unit length of $\pi^{*}$ and that
$L_{\pi^{*}}\geq 0$. Then

$\Delta(m_{i})=|m_{i}|-L_{\pi^{*}}d_{i}\geq|m_{i}|\geq\frac{n_{I}^{1/2}}{2c^{52}}-2+z=\Omega(r_{O}^{2/3}c^{-110})$

(The final inequality follows from part 1 of Proposition 6.) ∎

We now give a precise upper bound on $L_{\pi^{*}}$, the unit length of
$\pi^{*}$.

######  Proposition 7.

$L_{\pi^{*}}=O(r_{O}^{-1/3}c^{-110})$, and specifically,

$L_{\pi^{*}}\leq\frac{n_{I}^{1/2}c^{50}\cdot(2(c^{102}-c))^{-1}+z}{r_{O}-r_{O}^{-1/3}}$

###### Proof.

Recall that $z$ is the length of all subdivided paths in $G$. Note that every
move $m$ in path $\pi^{*}$ is a forward move with the same move vector
$\vec{m}=\vec{v}^{*}$ and will have the same path length $|m|$. Then an upper
bound for $|m|\cdot\|\vec{v}^{*}\|^{-1}$ will give an upper bound for
$L_{\pi^{*}}$. By property 1 of Lemma 7, $\|\vec{v}^{*}\|\geq
r_{O}-r_{O}^{-1/3}$ for sufficiently large $r_{O}$. Note that the length of
$m$ is the length of the canonical inner graph path corresponding to
$\pi^{*}$, plus the length $z$ of the subdivided path taken by $m$. By part 2
of Proposition 6, every canonical path in $G_{I}$ is of length at most
$(n_{I}^{1/2}c^{50})/(2(c^{102}-c))$. Then combining these observations,

$L_{\pi^{*}}=\frac{|m|}{\|\vec{v}^{*}\|}\leq\frac{(n_{I}^{1/2}c^{50})\cdot(2(c^{102}-c))^{-1}+z}{r_{O}-r_{O}^{-1/3}}$

as claimed. For sufficiently large $c,r_{O}$, we find that
$L_{\pi^{*}}\leq\frac{4n_{I}^{1/2}}{r_{O}c^{52}}=O(r_{O}^{-1/3}c^{-110})$. ∎

We now lower bound the move length difference $\Delta(m_{i})$ of zigzag moves.
We will see that because we specified that the vectors in our set $W_{O}$ lie
in a small cone with inner angle $\psi_{1}=c^{-5}$ (see property 4 of Lemma
8), zigzag moves will be quite inefficient compared to canonical moves.

######  Lemma 12.

Let $m_{i}$ be a move in Zigzag. Then
$\Delta(m_{i})=\Omega(r_{O}^{2/3}c^{-111})$.

###### Proof.

Observe that in a zigzag move, we first take some vector $-\vec{u}_{1}$ for
some $\vec{u}_{1}\in W_{O}$, and then we take some other vector $\vec{u}_{2}$
with $\vec{u}_{2}\in W_{O}$. Then $\vec{m}_{i}=\vec{u}_{2}-\vec{u}_{1}$. Since
$\vec{u}_{1},\vec{u}_{2}\in W_{O}$, the angle between vector $\vec{u}_{1}$ and
$\vec{u}_{2}$ is at most $c^{-5}$ by property 4 of Lemma 8. Then since
$r_{O}-r_{O}^{-1/3}\leq\|\vec{u}_{1}\|\leq r_{O}$ and
$r_{O}-r_{O}^{-1/3}\leq\|\vec{u}_{2}\|\leq r_{O}$, some straightforward
geometry shows that $\|\vec{m}_{i}\|\leq 2r_{O}^{-1/3}+c^{-5}\cdot r_{O}$.

Then $d_{i}\leq\|\vec{m}_{i}\|\leq 2c^{-5}\cdot r_{O}$ for sufficiently large
$r_{O}$. Additionally, observe that move $m_{i}$ takes two subdivided paths in
$G$, so $|m_{i}|\geq 2z=\Omega(r_{O}^{2/3}c^{-111})$. Then

$\Delta(m_{i})=|m_{i}|-L_{\pi^{*}}d_{i}\geq|m_{i}|-L_{\pi^{*}}2c^{-5}r_{O}\geq
2z-O(r_{O}^{2/3}c^{-115})=\Omega(r_{O}^{2/3}c^{-111})$

for sufficiently large $c$. ∎

Now to analyze the forward moves in $\mathcal{M}$, we find it useful to
partition the set Forward into sets Forward-S and Forward-D, depending on the
vector in $W_{O}$ corresponding to the subdivided path taken in the move. Let
$m$ be a move in Forward. Then $m$ is in Forward-S if move vector $\vec{m}\in
W_{O}$ belongs to the same stripe as vector $\vec{v}^{*}$ in $W_{O}$.
Otherwise, move vector $\vec{m}$ belongs to a different stripe than
$\vec{v}^{*}$ and $m$ is in Forward-D. We first analyze moves in Forward-D.

######  Proposition 8.

Let $\vec{u},\vec{v}$ be two vectors in $W_{O}$ that belong to different
stripes. Then $\texttt{proj}_{\vec{v}}\vec{u}\leq r_{O}(1-\sigma)$, where
$\sigma=4^{-1}c^{-20}$. Consequently, if $m_{i}$ is a move in Forward-D, then
$d_{i}\leq r_{O}(1-\sigma)$.

###### Proof.

By property 4a of Lemma 8, the angle $\psi$ between $\vec{u}$ and $\vec{v}$ is
at least $\psi_{2}=c^{-10}$ radians. Then from the Taylor expansion of $\cos
x$, we get that $\texttt{proj}_{\vec{v}}\vec{u}=\|\vec{u}\|\cos\psi\leq
r_{O}\cdot(1-\psi^{2}/2+\psi^{4}/4!)\leq r_{O}(1-\sigma)$ for sufficiently
large $c$. Now note that if $m_{i}$ is a move in Forward-D, then
$d_{i}=\texttt{proj}_{\vec{v}^{*}}\vec{m}_{i}\leq r_{O}(1-\sigma)$. ∎

Proposition 8 tells us that if a move $m_{i}$ is in Forward-D, then it loses a
constant fraction $\sigma$ of its move distance $d_{i}$. This follows from the
fact that $\vec{m}_{i}$ is in a different stripe than $\vec{v}^{*}$, so move
vector $\vec{m}_{i}$ is not travelling as far in the direction of
$\vec{v}^{*}$. (See Figure 7 for reference.) This deficiency in $d_{i}$ makes
moves in Forward-D inefficient compared to canonical moves, as we prove in the
following lemma.

######  Lemma 13.

Let $m_{i}$ be a move in Forward-D. Then
$\Delta(m_{i})=\Omega(r_{O}^{2/3}c^{-130})$.

###### Proof.

Since $m_{i}$ is a move in Forward-D, it follows that $d_{i}\leq
r_{O}(1-\sigma)$ by Proposition 8. Note that the length of $m_{i}$ is the
length of the inner graph traversal of $G_{I}$ in $m_{i}$ plus the length $z$
of the subdivided path taken by $m$. Then by part 1 of Proposition 6, move
$m_{i}$ requires at least $(n_{I}^{1/2})/(2c^{52})-2$ edges to travel from an
input port in $G_{I}$ to an output port. The length of the subdivided path
taken by $m_{i}$ is $z$, so $|m_{i}|\geq(n_{I}^{1/2})/(2c^{52})-2+z$. We
calculate $\Delta(m_{i})$ as follows.

$\displaystyle\Delta(m_{i})$ $\displaystyle=|m_{i}|-L_{\pi^{*}}d_{i}$
$\displaystyle\geq|m_{i}|-\frac{n_{I}^{1/2}c^{50}\cdot(2(c^{102}-c))^{-1}+z}{r_{O}-r_{O}^{-1/3}}\cdot
r_{O}(1-\sigma)$ by Prop. 7, 8
$\displaystyle\geq|m_{i}|-(n_{I}^{1/2}c^{50}\cdot(2(c^{102}-c))^{-1}+z)\cdot(1+2r_{O}^{-4/3})\cdot(1-\sigma)$
$\displaystyle\geq\left(\frac{n_{I}^{1/2}}{2c^{52}}-2+z\right)-\left(\frac{n_{I}^{1/2}c^{50}}{2(c^{102}-c)}+z\right)\cdot(1-\sigma)-O(r_{O}^{-2/3})$
by Prop. 6
$\displaystyle\geq\frac{n_{I}^{1/2}}{2c^{52}}-\frac{n_{I}^{1/2}c^{50}}{2(c^{102}-c)}\cdot(1-\sigma)-O(r_{O}^{-2/3})$
$\displaystyle\geq\left(\frac{n_{I}^{1/2}}{2c^{52}}-\frac{n_{I}^{1/2}c^{50}}{2(c^{102}-c)}\right)+\frac{n_{I}^{1/2}c^{50}}{2(c^{102}-c)}\sigma-O(r_{O}^{-2/3})$
$\displaystyle\geq-\frac{n_{I}^{1/2}}{c^{153}}+\frac{n_{I}^{1/2}}{8c^{72}}-O(r_{O}^{-2/3})=\Omega(r_{O}^{2/3}c^{-130})$
∎

We have shown that $\Delta(m_{i})=\Omega(r_{O}^{2/3}c^{-130})$ if $m_{i}$ is a
move in Backward, Zigzag, or Forward-D. Moreover, if $m_{i}$ is a move in
Stationary, then $\Delta(m_{i})\geq 0$ since $\vec{m}_{i}=\vec{0}$. However,
it’s not true in general that $\Delta(m_{i})\geq 0$ if $m_{i}$ is a move in
Forward-S. This is essentially because $m_{i}$ can take an
$(S_{I},T_{I})$-path in $G_{I}$ that is possibly much shorter than the
canonical inner graph path used by $\pi^{*}$. In the following section we will
introduce our inner graph potential function $\Phi$, and show that in an
amortized sense, moves in Forward-S are not shorter than the moves in
$\pi^{*}$.

###  6.2 Lower Bounding the Amortized Move Difference $\widehat{\Delta}$

Let $(s^{*},t^{*})\in P_{I}$ be the inner graph critical pair whose canonical
path $\pi_{I}^{s^{*},t^{*}}$ is a subpath of $\pi^{*}$ in $G_{I}$, and let
$s^{*}:=(s_{1}^{*},s_{2}^{*})$ and $t^{*}:=(t_{1}^{*},t_{2}^{*})$. Note that
by construction of $G$, $(s^{*},t^{*})=\phi(\vec{v}^{*})$. Additionally, let
$\vec{v}_{I}^{*}:=(v_{I,1}^{*},v_{I,2}^{*})=(r_{I}-c+i^{*},\sum_{j=i^{*}}^{c}j)\in
W_{I}$ be the canonical inner graph vector corresponding to critical pair
$(s^{*},t^{*})\in P_{I}$, where $i^{*}\in[1,c]$. Then for
$s_{i}=(s_{i,1},s_{i,2})\in S_{I}$ we define our inner graph potential
function $\Phi$ to be

$\Phi(s_{i})=\frac{s_{i,2}\cdot(i^{*})^{-1}+s_{i,1}}{r_{I}-c+i^{*}}$

Roughly, we may think of $\Phi(s_{i})$ as the capacity for path $\pi$ to have
future moves $m_{j}$, $j\geq i$ with move length difference $\Delta(m_{j})<0$.
The potential function $\Phi$ will be essential for analyzing the moves in
Forward-S. However, first we verify that the introduction of $\Phi$ does not
affect our existing lower bounds on the move length differences of moves in
Backward, Zigzag, Forward-D, or Stationary.

######  Proposition 9.

Let $m_{i}$ be a move in $\textsc{Backward},\textsc{Zigzag},$ or Forward-D.
Then $\widehat{\Delta}(m_{i})=\Theta(\Delta(m_{i}))$.

###### Proof.

To prove this claim we need to upper bound $\Phi(s_{i+1})-\Phi(s_{i})$. Recall
from our construction of $G_{I}$ that $S_{I}=[1,r_{I}/2]\times[1,y_{I}/2]$.
Now observe that $\Phi(\cdot)\geq 0$, and $\Phi(s_{i})$ is maximized when
$s_{i,1}=r_{I}/2$ and
$s_{i,2}=y_{I}/2=n_{I}^{1/2}c^{-50}=\Theta(r_{O}^{2/3}c^{-108})$. In this
case,

$\Phi(s_{i})=\frac{s_{i,2}\cdot(i^{*})^{-1}+s_{i,1}}{r_{I}-c+i^{*}}\leq\frac{4s_{i,2}}{r_{I}}=O(r_{O}^{2/3}\cdot
c^{-210})$

Then $\Phi(s_{i+1})-\Phi(s_{i})=O(r_{O}^{2/3}\cdot c^{-210})$. Now recall that
by Lemmas 11, 12, and 13, $\Delta(m_{i})=\Omega(r_{O}^{2/3}c^{-130})$. Then
the claim immediately follows by taking $c$ to be sufficiently large. ∎

We can also lower bound the amortized move length difference of stationary
moves.

######  Lemma 14.

Let $m_{i}$ be a move in Stationary. Then $\widehat{\Delta}(m_{i})\geq 0$.

###### Proof.

Observe that $d_{i}=0$ because we stay in the same inner graph copy in this
move, so $\vec{m}_{i}=\vec{0}$. Then
$\widehat{\Delta}(m_{i})=|m_{i}|-(\Phi(s_{i+1})-\Phi(s_{i}))$. Let
$s_{i}=(s_{i,1},s_{i,2})$ and let $s_{i+1}=(s_{i+1,1},s_{i+1,2})$. Observe
that $s_{i+1,1}-s_{i,1}\leq r_{I}/2$ since $s_{i},s_{i+1}\in S_{I}$. Let
$m_{i}^{I}$ be the subpath of $m_{i}$ restricted to inner graph copy
$G_{I}^{(i)}$. Note that $|m_{i}|\geq|m_{i}^{I}|$. Suppose that
$|m_{i}^{I}|=d$ for some integer $d>0$. Now note that for all vectors
$\vec{v}=(v_{1},v_{2})\in W_{I}\cup-W_{I}$, we have that $v_{1}\leq c^{2}$.
Then by the construction of $G_{I}$ it follows that $s_{i+1,2}-s_{i,2}\leq
dc^{2}$. Then using the fact that $r_{I}=c^{102}$ and $i^{*}\in[1,c]$,

$\Phi(s_{i+1})-\Phi(s_{i})=\Phi(s_{i+1}-s_{i})\leq\frac{dc^{2}\cdot(i^{*})^{-1}+r_{I}/2}{r_{I}-c+1}\leq
2dc^{-100}+2/3\leq d$

for sufficiently large $c$. Then
$\widehat{\Delta}(m_{i})\geq|m_{i}^{I}|-(\Phi(s_{i+1})-\Phi(s_{i}))\geq 0$ as
claimed. ∎

Before lower bounding $\widehat{\Delta}(m_{i})$ for moves $m_{i}$ in
Forward-S, we first define a geometric object associated with $m_{i}$ that
will be useful in our analysis.

######  Definition 11 (Displacement vector).

Let $m_{i}$ be a move from input port $s_{i}$ in $G_{I}^{(i)}$ to input port
$s_{i+1}$ in $G_{I}^{(i+1)}$, and let $t_{i}\in T_{I}$ be the output port
incident to the subdivided path taken by $m_{i}$ to reach $s_{i+1}$. The
displacement vector $\vec{\delta}_{i}=(\delta_{i,1},\delta_{i,2})$ of $m_{i}$
is defined as

$\vec{\delta}_{i}=(t_{i}-s_{i})-(t^{*}-s^{*}).$

Observe that intuitively, $\vec{\delta}_{i}$ corresponds to the difference
between the displacement from $s_{i}$ to $t_{i}$ and the displacement from
$s^{*}$ to $t^{*}$ in $\mathbb{Z}^{2}$. Despite being a purely geometric
notion, $\vec{\delta}_{i}$ has two key properties related to the structure of
graph $G$ that we will make use of in our analysis:

  * •

Update Property. If $m_{i}$ is a move in Forward-S, then $s_{i+1}$ is uniquely
determined by $s_{i}$ and $\vec{\delta}_{i}$. This property is formalized by
Proposition 10.

  * •

Graph Distance Property. The displacement vector $\vec{\delta}_{i}$ is tightly
connected to $d_{G_{I}}(s_{i},t_{i})$, the graph distance from $s_{i}$ to
$t_{i}$ in $G_{I}$. This property is formalized by Lemma 15.

As it turns out, these two properties will be sufficient to show that
$\widehat{\Delta}(m_{i})\geq 0$ for moves $m_{i}$ in Forward-S. We will
proceed by formalizing and proving the Update Property of $\vec{\delta}_{i}$.

######  Proposition 10 (Update Property).

Let $m_{i}$ be a move from $s_{i}$ to $s_{i+1}$ in Forward-S. Then

$s_{i+1}=s_{i}+\vec{\delta}_{i}.$

###### Proof.

In move $m_{i}$ we take a subdivided path plugged into output port
$t_{i}:=(t_{i,1},t_{i,2})\in T_{I}$ in $G_{I}^{(i)}$. This subdivided path
corresponds to the outer graph vector $\vec{m}_{i}\in W_{O}$. By the
construction of $\phi$, any such subdivided path will be plugged into an input
port $s_{i+1}$ of $G_{I}^{(i+1)}$ such that
$\phi(\vec{m}_{i})=(s_{i+1},t_{i})\in P_{I}$. By Proposition 4, for all
$(s_{i+1},t_{i})\in P_{I}$, $t_{i,1}-s_{i+1,1}=x_{I}-r_{I}/2$, where
$s_{i+1,1}$ denotes the first coordinate of $s_{i+1}$. Then
$s_{i+1,1}=t_{i,1}-(x_{I}-r_{I}/2)=t_{i,1}-(t_{1}^{*}-s_{1}^{*})$, since
$t_{1}^{*}-s_{1}^{*}=x_{I}-r_{I}/2$ by Proposition 4. Consequently,
$s_{i+1,1}=s_{i,1}+t_{i,1}-s_{i,1}-(t_{1}^{*}-s_{1}^{*})=s_{i,1}+\delta_{i,1}$.

Recall that since move $m_{i}$ is in Forward-S, vector $\vec{m}_{i}\in W_{O}$
is in the same stripe as $\vec{v}^{*}\in W_{O}$. Then by Proposition 5, the
critical pair $\phi(\vec{m}_{i})=(s_{i+1},t_{i})\in P_{I}$ has the same
canonical inner graph vector in $W_{I}$ as the critical pair
$\phi(\vec{v}^{*})=(s^{*},t^{*})\in P_{I}$. Namely, critical pairs
$\phi(\vec{m}_{i})$ and $\phi(\vec{v}^{*})$ share the canonical inner graph
vector $\vec{v}_{I}^{*}=(\vec{v}_{I,1}^{*},\vec{v}_{I,2}^{*})\in W_{I}$. Then
since $t_{i,1}-s_{i+1,1}=t_{1}^{*}-s_{1}^{*}$ (by Proposition 4), we have that

$\displaystyle t_{i,2}-s_{i+1,2}=v_{I,2}^{*}\cdot
t_{i,1}-s_{i+1,1})=(v_{I}^{*})_{y}\cdot(t_{x}^{*}-s_{x}^{*})=t_{y}^{*}-s_{y}^{*}$

by the construction of $P_{I}$. Then
$s_{y}^{i+1}=t_{y}^{i}-(t_{y}^{*}-s_{y}^{*})=s_{y}^{i}+\delta_{y}^{i}$. The
claim follows. ∎

The above proposition imposes a strong condition on the location of the next
input port after a move in Forward-S. We will use this proposition to argue
about how the inner graph potential $\Phi$ changes after a move in Forward-S.
See Figure 8 for a visualization of the Update Property acting on moves in
Forward-S.

Figure 8: Above, two consecutive moves in $\pi^{*}$. The dotted lines between
inner graphs represent subdivided paths in $G$. Note that all moves in
$\pi^{*}$ are forward moves that take inner graph path $\pi_{I}^{s^{*},t^{*}}$
and the subdivided path corresponding to vector $\vec{v}^{*}\in W_{O}$. Below,
two consecutive moves $m_{i}$, $m_{i+1}$ belonging to Forward-S in path $\pi$.
Here $m_{i}^{I}$ denotes the restriction of $m_{i}$ to inner graph
$G_{I}^{(i)}$. Vectors $t^{*}-s^{*}$ and $\vec{\delta}_{i}$ are depicted in
blue and purple respectively. Note that by the Update Property, $s_{i+1}$ is
uniquely determined by $s_{i}$ and $\vec{\delta}_{i}$. In particular,
$s_{i+1}=s_{i}+\vec{\delta}_{i}$. Likewise,
$s_{i+2}=s_{i+1}+\vec{\delta}_{i+1}$.

#### Graph Distance Property.

Before stating the graph distance property formally, we will first attempt to
convey an intuitive understanding of it. Because our graph $G_{I}$ is embedded
in $\mathbb{Z}^{2}$ and the edges in $G_{I}$ correspond to vectors
$W_{I}\subseteq\mathbb{Z}^{2}$, it is natural to imagine a correspondence
between distances in the Euclidean metric and distances in the graph metric of
$G_{I}$. Roughly, we might presume that vertices $s_{i},t_{i}$ in $G_{I}$ with
a large Euclidean distance $\|t_{i}-s_{i}\|$ in $\mathbb{Z}^{2}$ will have a
large graph distance $d_{G_{I}}(s_{i},t_{i})$ in $G_{I}$. This understanding
is approximately correct.

Suppose that $\delta_{x}^{i}\geq 0$. Then $t_{x}^{i}-s_{x}^{i}\geq
t_{x}^{*}-s_{x}^{*}$, so vertices $s_{i},t_{i}$ have a larger horizontal
displacement than vertices $s^{*},t^{*}$. Since all our edges
$\vec{w}=(w_{x},w_{y})\in W_{I}\cup-W_{I}$ in $G_{I}$ have horizontal
displacement at most $w_{x}\leq r_{I}$, we can imagine that we must travel on
more edges in $G_{I}$ to reach $t_{i}$ from $s_{i}$ than are needed to reach
$t^{*}$ from $s^{*}$. Likewise, if $\delta_{x}^{i}\leq 0$, then we can imagine
that we may travel on fewer edges in $G_{I}$ to reach $t_{i}$ from $s_{i}$
than are needed to reach $t^{*}$ from $s^{*}$.

Now suppose that $\delta_{y}^{i}\geq 0$. Then $t_{y}^{i}-s_{y}^{i}\geq
t_{y}^{*}-s_{y}^{*}$, so vertices $s_{i},t_{i}$ have a larger vertical
displacement than vertices $s^{*},t^{*}$. Then it follows that every
$(s_{i},t_{i})$-path in $G_{I}$ must attain a larger vertical displacement
than every $(s^{*},t^{*})$-path. Now note that by the construction of $W_{I}$,
edges $\vec{w}=(w_{x},w_{y})\in W_{I}\cup-W_{I}$ with a larger vertical
component $w_{y}$ have a smaller horizontal component $w_{x}$. Then we will
need to travel on more of these edges with smaller horizontal components in
order to reach $t_{i}$ from $s_{i}$. Thus we can imagine that more edges must
be traversed in $G_{I}$ to reach $t_{i}$ from $s_{i}$ than are needed to reach
$t^{*}$ from $s^{*}$. Likewise, if $\delta_{y}^{i}\leq 0$, then we can argue
that fewer edges are needed to travel from $s_{i}$ to $t_{i}$, since we can
travel on edges in $W_{I}$ with larger horizontal components.

If we examine the moves $m_{i}$ and $m_{i+1}$ in Figure 8, our intuition would
suggest that $d_{G_{I}}(s_{i},t_{i})\gg d_{G_{I}}(s^{*},t^{*})$, since
$t_{y}^{i}-s_{y}^{i}\gg t_{y}^{*}-s_{y}^{*}$. Likewise, our intuition would
suggest that $d_{G_{I}}(s_{i+1},t_{i+1})\ll d_{G_{I}}(s^{*},t^{*})$, since
$t_{y}^{i+1}-s_{y}^{i+1}\ll t_{y}^{*}-s_{y}^{*}$. To summarize, our
(completely informal) argument suggests that the graph distance
$d_{G_{I}}(s_{i},t_{i})$ increases with $\delta_{x}^{i}$ and $\delta_{y}^{i}$.
We now present Lemma 15, which states our precise formalization of the Graph
Distance Property.

######  Lemma 15 (Graph Distance Property).

Let $s_{i}$ be an input port in $S_{I}$, and let $t_{i}$ be an output port in
$T_{I}$, where $t_{i}$ is incident to a subdivided path in $G$. Suppose that
$d_{G_{I}}(s_{i},t_{i})=|\pi_{I}^{s^{*},t^{*}}|+d$, for some integer $d$. Then

$\frac{\delta_{y}^{i}\cdot(i^{*})^{-1}+\delta_{x}^{i}}{r_{I}-c+i^{*}}\leq d$

###### Proof.

This lemma requires a precise and technical analysis of graph distances in
$G_{I}$, so we defer its proof to Section 6.3. ∎

Notice that the lower bound on $d_{G_{I}}(s_{i},t_{i})$ in Lemma 15 increases
as $\delta_{x}^{i}$ and $\delta_{y}^{i}$ increase, matching our intuitive
understanding of distances in $G_{I}$. Now that we have formally stated our
two properties of $\vec{\delta}_{i}$, we are ready to lower bound the
amortized move length difference $\widehat{\Delta}(m_{i})$ for moves $m_{i}$
in Forward-S.

######  Lemma 16.

Let $m_{i}$ be a move in Forward-S. Then $\widehat{\Delta}(m_{i})\geq 0$.

###### Proof.

Let $m_{i}^{I}$ be the restriction of $m_{i}$ to inner graph copy
$G_{I}^{(i)}$. Then $|m_{i}|=|m_{i}^{I}|+z$. Additionally, $m_{i}^{I}$ must
begin at some input port $s_{i}\in S_{I}$ and end at some output port
$t_{i}\in T_{I}$, where $t_{i}$ is incident to a subdivided path. Note that
$d_{G_{I}}(s_{i},t_{i})\leq|m_{i}^{I}|$. Now recall that
$L_{\pi^{*}}=\frac{|\pi_{I}^{s^{*},t^{*}}|+z}{\|\vec{v}^{*}\|}$ and observe
the following:

$\displaystyle\Delta(m_{i})$ $\displaystyle=|m_{i}|-L_{\pi^{*}}\cdot d_{i}$
$\displaystyle=|m_{i}^{I}|+z-\frac{|\pi_{I}^{s^{*},t^{*}}|+z}{\|\vec{v}^{*}\|}\cdot
d_{i}$
$\displaystyle\geq|m_{i}^{I}|+z-\frac{|\pi_{I}^{s^{*},t^{*}}|+z}{\|\vec{v}^{*}\|}\cdot\|\vec{v}^{*}\|$
by Property 3 of Lemma 7
$\displaystyle\geq|m_{i}^{I}|-|\pi_{I}^{s^{*},t^{*}}|$

Now let $d_{G_{I}}(s_{i},t_{i})=|\pi_{I}^{s^{*},t^{*}}|+d$ for some integer
$d$. Then

$\displaystyle\widehat{\Delta}(m_{i})$
$\displaystyle\geq|m_{i}^{I}|-|\pi_{I}^{s^{*},t^{*}}|-(\Phi(s_{i+1})-\Phi(s_{i}))$
$\displaystyle\geq d-(\Phi(s_{i+1})-\Phi(s_{i}))$
$\displaystyle=d-\frac{(s_{y}^{i+1}-s_{y}^{i})(i^{*})^{-1}+(s^{i+1}_{x}-s^{i}_{x})}{r_{I}-c+i^{*}}$
$\displaystyle=d-\frac{\delta_{y}^{i}\cdot(i^{*})^{-1}+\delta_{x}^{i}}{r_{I}-c+i^{*}}$
by Proposition 10 $\displaystyle\geq d-d$ by Lemma 15 $\displaystyle\geq 0$

∎

With the exception of the proof of Lemma 15, which has been deferred to
Section 6.3, we have established lower bounds for the amortized move
difference $\widehat{\Delta}$ of all moves in the moveset. We will finish our
lower bound argument in Section 6.4.

###  6.3 Proving Lemma 15 (Graph Distance Property)

We will prove the following inequality, which is equivalent to the one stated
in Lemma 15:

$\delta_{y}^{i}\leq i^{*}(d(r_{I}-c+i^{*})-\delta_{x}^{i})$

Let $s_{i}:=(s_{x},s_{y})\in S_{I}$, and let $t_{i}:=(t_{x},t_{y})\in T_{I}$,
where $t_{i}$ is incident to a subdivided path in $G$. Let $\pi_{i}$ be a
shortest $(s_{i},t_{i})$-path of length $\ell=|\pi_{I}^{s^{*},t^{*}}|+d$ in
$G_{I}$. Corresponding to $\pi_{i}$, we define the vector
$\vec{v}=(v_{x},v_{y})=t_{i}-s_{i}$. Let
$\vec{v}_{1},\vec{v}_{2},\dots,\vec{v}_{\ell}$ be the vectors corresponding to
the edges of $\pi_{i}$ and observe that
$\vec{v}=\sum_{i=1}^{\ell}\vec{v}_{i}$. Furthermore, $\vec{v}_{i}\in
W_{I}\cup-W_{I}$ for $i\in[1,\ell]$. Additionally, we define the vector
$\vec{u}=(u_{x},u_{y})=\sum_{i=1}^{\ell}\vec{v}_{I}^{*}$.

Observe that the quantity we want to upper bound is
$\delta_{y}^{i}=(t_{y}-s_{y})-(t_{y}^{*}-s_{y}^{*})=v_{y}-(t_{y}^{*}-s_{y}^{*})$.
We find that it easiest to separately upper bound $\delta_{1}=v_{y}-u_{y}$ and
$\delta_{2}=u_{y}-(t_{y}^{*}-s_{y}^{*})$. Then since
$\delta_{y}^{i}=\delta_{1}+\delta_{2}$, this will give us an upper bound of
$\delta_{y}^{i}$ as desired. We first find the precise value of $\delta_{2}$.

######  Proposition 11.

$\delta_{2}=d\cdot\sum_{j=i^{*}}^{c}j$

###### Proof.

We find the precise value of $\delta_{2}$ by observing that since
$\vec{u}=|\pi_{I}^{s^{*},t^{*}}|\cdot\vec{v}_{I}^{*}+d\vec{v}_{I}^{*}=t^{*}-s^{*}+d\vec{v}_{I}^{*}$,
it follows that

$\delta_{2}=u_{y}-(t_{y}^{*}-s_{y}^{*})=d\cdot\sum_{j=i^{*}}^{c}j$

where the final equality follows from the fact that
$\vec{v}_{I}^{*}=((v_{I}^{*})_{x},(v_{I}^{*})_{y})=(r_{I}-c+i^{*},\sum_{j=i^{*}}^{c}j)$.
∎

For the rest of the proof, we will make use of the fact that
$\sum_{j=i}^{c}j=-i(i-1)/2+c(c+1)/2\geq 0$ for $i\in[1,c]$. Before upper
bounding $\delta_{1}$, we first observe that by Proposition 4,

$\displaystyle v_{x}-u_{x}$
$\displaystyle=v_{x}-(t^{*}_{x}-s^{*}_{x})-d\cdot(v_{I}^{*})_{x}$
$\displaystyle=\delta_{x}^{i}-d\cdot(v_{I}^{*})_{x}$
$\displaystyle=\delta_{x}^{i}-d(r_{I}-c+i^{*})$

Moreover, since $s_{i}\in S_{I}$, $1\leq s_{x}\leq r_{I}/2$. Likewise, since
$t_{i}\in T_{I}$, $x_{I}-r_{I}\leq t_{i}\leq x_{I}$. However, since $t_{i}$ is
incident to a subdivided path, it follows by Proposition 4 that the horizontal
displacement between $t_{i}$ and some input port in $S_{I}$ is exactly
$x_{I}-r_{I}/2$. Consequently, we obtain the stronger condition that
$x_{I}-r_{I}/2+1\leq t_{i}\leq x_{I}$. Then since $v_{x}=t_{x}-s_{x}$, it
follows that $x_{I}-r_{I}\leq v_{x}\leq x_{I}$. Finally, since
$v_{x}-(t_{x}^{*}-s_{x}^{*})=\delta_{x}^{i}$, we conclude that

$-r_{I}/2\leq\delta_{x}^{i}\leq r_{I}/2.$

Now we can upper bound $\delta_{1}$ by upper bounding the solution of the
following optimization problem IP1:

IP1: maximize $\displaystyle
v_{y}-u_{y}=\sum_{i=1}^{\ell}((v_{i})_{y}-(v_{I}^{*})_{y})$ subject to
$\displaystyle v_{x}-u_{x}=\sum_{i=1}^{\ell}((v_{i})_{x}-(v_{I}^{*})_{x})$
$\displaystyle\vec{v}_{i}=((v_{i})_{x},(v_{i})_{y})\in W_{I}\cup-W_{I}\text{
for }i\in[1,\ell]$

We now perform the following change of variables. Let

$\vec{q}_{i}:=\vec{v}_{i}-\vec{v}_{I}^{*}\qquad\text{ for }i\in[1,\ell]$

Then the constraint that $\vec{v}_{i}\in W_{I}\cup-W_{I}$ becomes
$\vec{q}_{i}\in Q_{1}\cup Q_{2}$, where

$Q_{1}:=W_{I}-\vec{v}_{I}^{*}=\left\\{\left(i-i^{*},\frac{-i(i-1)+i^{*}(i^{*}-1)}{2}\right)\bigm{|}i\in[1,c]\right\\}$

and

$Q_{2}:=-W_{I}-\vec{v}_{I}^{*}=\left\\{\left(-i-2r_{I}+2c-i^{*},\frac{i(i-1)+i^{*}(i^{*}-1)}{2}-c(c+1)\right)\bigm{|}i\in[1,c]\right\\}.$

Set $Q_{1}$ corresponds to the translated vectors from $W_{I}$ and $Q_{2}$
corresponds to the translated vectors from $-W_{I}$. We now give a linear
relaxation of IP1:

LP1: $\displaystyle\text{maximize }\qquad\delta_{1}^{\prime}=$
$\displaystyle\sum_{\vec{q}\in Q_{1}\cup Q_{2}}q_{y}w_{\vec{q}}$ subject to
$\displaystyle\sum_{\vec{q}\in Q_{1}\cup Q_{2}}q_{x}w_{\vec{q}}=v_{x}-u_{x}$
$\displaystyle w_{\vec{q}}\geq 0\text{ for }\vec{q}\in Q_{1}\cup Q_{2}$

Note that $\delta_{1}^{\prime}\geq\delta_{1}$, since any feasible solution
$\\{\vec{v}_{i}\\}_{i\in[1,\ell]}$ to IP1 can be converted to a feasible
solution $\\{w_{\vec{q}}\\}_{\vec{q}\in Q_{1}\cup Q_{2}}$ in LP1 with the same
value. Thus it will be sufficient for our purposes to upper bound
$\delta_{1}^{\prime}$. To that end, we observe the following useful fact about
solutions to LP1. This fact, expressed in Proposition 12, follows
straightforwardly from a convexity property of $Q_{1}$ and $Q_{2}$. We will
defer the proof of Proposition 12 to Appendix B.

######  Proposition 12.

There exist optimal solutions to LP1 that are of the form

$\delta_{1}^{\prime}=w_{\vec{q}_{1}}\cdot(q_{1})_{y}+w_{\vec{q}_{2}}\cdot(q_{2})_{y}$

where $\vec{q}_{1}=((q_{1})_{x},(q_{1})_{y})\in Q_{1}$,
$\vec{q}_{2}=((q_{2})_{x},(q_{2})_{y})\in Q_{2}$, and
$w_{\vec{q}_{1}}\cdot(q_{1})_{x}+w_{\vec{q}_{2}}\cdot(q_{2})_{x}=v_{x}-u_{x}$.

###### Proof.

Deferred to Appendix B. ∎

For the remainder of the proof, we split our analysis into three cases:

  * •

Case 1: $v_{x}-u_{x}>0$

  * •

Case 2: $v_{x}-u_{x}<0$

  * •

Case 3: $v_{x}-u_{x}=0$

We begin with Case 1.

######  Proposition 13 (Case 1).

If $v_{x}-u_{x}>0$, then $\delta_{y}^{i}\leq
i^{*}(d(r_{I}-c+i^{*})-\delta_{x}^{i})$.

###### Proof.

We may assume our solution is of the form
$\delta_{1}^{\prime}=w_{\vec{q}_{1}}\cdot(q_{1})_{y}+w_{\vec{q}_{2}}\cdot(q_{2})_{y}$
subject to $\vec{q}_{1}\in Q_{1}$, $\vec{q}_{2}\in Q_{2}$, and
$w_{\vec{q}_{1}}\cdot(q_{1})_{x}+w_{\vec{q}_{2}}\cdot(q_{2})_{x}=v_{x}-u_{x}$.
First note that $(q_{2})_{x}<0$ and $(q_{2})_{y}<0$ for all $\vec{q}_{2}\in
Q_{2}$, so it follows that $(q_{1})_{x}>0$. Then by the definition of $Q_{1}$,
$(q_{1})_{y}<0$. Then the following feasible solution will be at least as good
as our initial solution:

$\delta_{1}^{\prime}=w^{\prime}_{\vec{q}_{1}}\cdot(q_{1})_{y},\text{\quad
where \quad}w^{\prime}_{\vec{q}_{1}}:=(v_{x}-u_{x})/(q_{1})_{x}$

  * •

Feasible: Note that $v_{x}-u_{x}>0$ and $(q_{1})_{x}>0$, so
$w^{\prime}_{\vec{q}_{1}}>0$ as required. Additionally, the constraint
$w^{\prime}_{\vec{q}_{1}}\cdot(q_{1})_{x}=v_{x}-u_{x}$ is satisfied.

  * •

Optimal: The difference between the value of our new solution and our old
solution is

$\displaystyle
w^{\prime}_{\vec{q}_{1}}\cdot(q_{1})_{y}-(w_{\vec{q}_{1}}\cdot(q_{1})_{y}+w_{\vec{q}_{2}}\cdot(q_{2})_{y})$
$\displaystyle=(v_{x}-u_{x})\cdot\frac{(q_{1})_{y}}{(q_{1})_{x}}-(w_{\vec{q}_{1}}\cdot(q_{1})_{y}+w_{\vec{q}_{2}}\cdot(q_{2})_{y})$
$\displaystyle=(w_{\vec{q}_{1}}\cdot(q_{1})_{x}+w_{\vec{q}_{2}}\cdot(q_{2})_{x})\cdot\frac{(q_{1})_{y}}{(q_{1})_{x}}-(w_{\vec{q}_{1}}\cdot(q_{1})_{y}+w_{\vec{q}_{2}}\cdot(q_{2})_{y})$
$\displaystyle=w_{\vec{q}_{2}}\left(\frac{(q_{2})_{x}(q_{1})_{y}}{(q_{1})_{x}}-(q_{2})_{y}\right)\geq
0$

The inequality follows from the fact that $(q_{1})_{x}>0$, $(q_{1})_{y}<0$,
$(q_{2})_{x}<0$, and $(q_{2})_{y}<0$ as noted earlier in the proof. We
conclude our new solution is at least as good as the initial solution.

Consequently, we may assume that our solution is of the form
$\delta_{1}^{\prime}=w_{\vec{q}_{1}}(q_{1})_{y}$, where
$w_{\vec{q}_{1}}(q_{1})_{x}=v_{x}-u_{x}$. This term is maximized when we
choose $\vec{q}_{1}\in Q_{1}$ to be the vector with the maximum
$\frac{(q_{1})_{y}}{(q_{1})_{x}}$ ratio, where $(q_{1})_{x}>0$. It is
straightforward to verify that vector $(1,-i^{*})\in Q_{1}$ has the maximum
such ratio $\frac{(q_{1})_{y}}{(q_{1})_{x}}=-i^{*}$.

We conclude that
$\delta_{1}\leq\delta_{1}^{\prime}=\frac{(q_{1})_{y}}{(q_{1})_{x}}\cdot(v_{x}-u_{x})=-i^{*}(v_{x}-u_{x})$.
Recall that $v_{x}-u_{x}=\delta_{x}^{i}-d(r_{I}-c+i^{*})$ and
$-r_{I}/2\leq\delta_{x}^{i}\leq r_{I}/2$. Then since $0\leq v_{x}-u_{x}$, it
follows that $d\leq\delta_{x}^{i}/(r_{I}-c+i^{*})<1$. Consequently, $d\leq 0$.
Then

$\displaystyle\delta_{y}^{i}$ $\displaystyle=\delta_{1}+\delta_{2}$
$\displaystyle\leq-i^{*}(v_{x}-u_{x})+d\cdot\sum_{j=i^{*}}^{c}j$
$\displaystyle\leq i^{*}(u_{x}-v_{x})=i^{*}(d(r_{I}-c+i^{*})-\delta_{x}^{i}),$

as desired. ∎

######  Proposition 14 (Case 2).

If $v_{x}-u_{x}<0$, then $\delta_{y}^{i}\leq
i^{*}(d(r_{I}-c+i^{*})-\delta_{x}^{i})$.

###### Proof.

Again we may assume our solution is of the form
$\delta_{1}^{\prime}=w_{\vec{q}_{1}}\cdot(q_{1})_{y}+w_{\vec{q}_{2}}\cdot(q_{2})_{y}$,
where $\vec{q}_{1}\in Q_{1}$, $\vec{q}_{2}\in Q_{2}$, and
$w_{\vec{q}_{1}}\cdot(q_{1})_{x}+w_{\vec{q}_{2}}\cdot(q_{2})_{x}=v_{x}-u_{x}$.
It can be seen that $\delta_{1}^{\prime}\geq 0$ (e.g. by taking
$w_{\vec{q}_{2}}=0$ and $\vec{q}_{1}=(-1,i^{*}-1)\in Q_{1}$). Now note that
$(q_{2})_{x}<0$ and $(q_{2})_{y}<0$ for all $\vec{q}_{2}\in Q_{2}$.
Additionally, note that if $(q_{1})_{x}\geq 0$, then $(q_{1})_{y}\leq 0$.
Consequently, if $(q_{1})_{x}\geq 0$, then $\delta_{1}^{\prime}<0$, so we may
assume $(q_{1})_{x}<0$. Then since $(q_{1})_{x}<0$, it follows that
$(q_{1})_{y}>0$ by the definition of $Q_{1}$. On the other hand, we know that
$(q_{2})_{y}<0$, so the following feasible solution will be at least as good
as our initial solution:

$\delta_{1}^{\prime}=w^{\prime}_{\vec{q}_{1}}\cdot(q_{1})_{y},\text{\quad
where \quad}w^{\prime}_{\vec{q}_{1}}:=(v_{x}-u_{x})/(q_{1})_{x}$

  * •

Feasible: Note that $v_{x}-u_{x}>0$ and $(q_{1})_{x}>0$, so
$w^{\prime}_{\vec{q}_{1}}>0$ as required. Additionally, the constraint
$w^{\prime}_{\vec{q}_{1}}\cdot(q_{1})_{x}=v_{x}-u_{x}$ is satisfied.

  * •

Optimal: The difference between the value of our new solution and our old
solution is

$\displaystyle
w^{\prime}_{\vec{q}_{1}}\cdot(q_{1})_{y}-(w_{\vec{q}_{1}}\cdot(q_{1})_{y}+w_{\vec{q}_{2}}\cdot(q_{2})_{y})$
$\displaystyle=(v_{x}-u_{x})\cdot\frac{(q_{1})_{y}}{(q_{1})_{x}}-(w_{\vec{q}_{1}}\cdot(q_{1})_{y}+w_{\vec{q}_{2}}\cdot(q_{2})_{y})$
$\displaystyle=(w_{\vec{q}_{1}}\cdot(q_{1})_{x}+w_{\vec{q}_{2}}\cdot(q_{2})_{x})\cdot\frac{(q_{1})_{y}}{(q_{1})_{x}}-(w_{\vec{q}_{1}}\cdot(q_{1})_{y}+w_{\vec{q}_{2}}\cdot(q_{2})_{y})$
$\displaystyle=w_{\vec{q}_{2}}\left(\frac{(q_{2})_{x}(q_{1})_{y}}{(q_{1})_{x}}-(q_{2})_{y}\right)\geq
0$

The inequality follows from the fact that $(q_{1})_{x}<0$, $(q_{1})_{y}>0$,
$(q_{2})_{x}<0$, and $(q_{2})_{y}<0$ as noted earlier in the proof. We
conclude our new solution is at least as good.

Then we may assume our solution is of the form $w_{\vec{q}_{1}}(q_{1})_{y}$,
where $w_{\vec{q}_{1}}(q_{1})_{x}=v_{x}-u_{x}$. This term is maximized when we
choose $\vec{q}_{1}$ to be the vector with the maximum
$-\frac{(q_{1})_{y}}{(q_{1})_{x}}$ ratio, where $(q_{1})_{x}<0$. It is
straightforward to verify that vector $(-1,i^{*}-1)\in Q_{1}$ has the maximum
such ratio $-\frac{(q_{1})_{y}}{(q_{1})_{x}}=i^{*}-1$.

We conclude that
$\delta_{1}\leq\delta_{1}^{\prime}=-\frac{(q_{1})_{y}}{(q_{1})_{x}}\cdot(v_{x}-u_{x})=-(i^{*}-1)(v_{x}-u_{x})$.
Recall that $v_{x}-u_{x}=\delta_{x}^{i}-d(r_{I}-c+i^{*})$ and
$-r_{I}/2\leq\delta_{x}^{i}\leq r_{I}/2$. Then since $0\geq v_{x}-u_{x}$, it
follows that $d\geq\delta_{x}^{i}/(r_{I}-c+i^{*})>-1$. Consequently, $d\geq
0$. Now note that if $d=0$, then

$\delta_{y}^{i}=\delta_{1}+\delta_{2}=\delta_{1}\leq(i^{*}-1)(u_{x}-v_{x})\leq
i^{*}(d(r_{I}-c+i^{*})-\delta_{x}^{i})$

where the final inequality follows from the fact that $u_{x}-v_{x}>0$.
Otherwise, if $d>0$, then

$\displaystyle\delta_{y}^{i}=\delta_{1}+\delta_{2}$
$\displaystyle\leq(i^{*}-1)\cdot(d(r_{I}-c+i^{*})-\delta_{x}^{i})+d\cdot\sum_{j=i^{*}}^{c}j$
$\displaystyle\leq
i^{*}\cdot(d(r_{I}-c+i^{*})-\delta_{x}^{i})-(d(r_{I}-c+i^{*})-\delta_{x}^{i})+dc^{2}$
$\displaystyle\leq
i^{*}\cdot(d(r_{I}-c+i^{*})-\delta_{x}^{i})-d(r_{I}-c^{2}-c)+\delta_{x}^{i}$
$\displaystyle\leq
i^{*}\cdot(d(r_{I}-c+i^{*})-\delta_{x}^{i})-r_{I}/2+\delta_{x}^{i}$
$\displaystyle\leq
i^{*}\cdot(d(r_{I}-c+i^{*})-\delta_{x}^{i})-r_{I}/2+r_{I}/2$
$\displaystyle=i^{*}(d(r_{I}-c+i^{*})-\delta_{x}^{i})$

∎

######  Proposition 15 (Case 3).

If $v_{x}-u_{x}=0$, then $\delta_{y}^{i}\leq
i^{*}(d(r_{I}-c+i^{*})-\delta_{x}^{i})$.

###### Proof.

Assume our solution is of the form
$\delta_{1}^{\prime}=w_{\vec{q}_{1}}\cdot(q_{1})_{y}+w_{\vec{q}_{2}}\cdot(q_{2})_{y}$.
By taking $w_{\vec{q}_{1}}=w_{\vec{q}_{2}}=0$, we see that
$\delta_{1}^{\prime}\geq 0$. Moreover, if $w_{\vec{q}_{2}}>0$, then
$\delta_{1}^{\prime}<0$, so we may assume $w_{\vec{q}_{2}}=0$. Then
$\vec{q}_{1}=(0,0)\in Q_{1}$, so $\delta_{1}\leq\delta_{1}^{\prime}=0$.
Additionally, by the arguments in the previous two cases, $d=0$. Then

$\delta_{y}^{i}=\delta_{1}+\delta_{2}=0=u_{x}-v_{x}=d(r_{I}-c+i^{*})-\delta_{x}^{i}\leq
i^{*}(d(r_{I}-c+i^{*})-\delta_{x}^{i}).$

∎

Lemma 15 follows immediately from Propositions 13, 14, 15.

###  6.4  Finishing the Lower Bound

Now that we have lower bounds for every category of move, we can begin
reasoning about the difference in lengths between $\pi$ and $\pi^{*}$.

######  Lemma 17.

Let $\pi$ be an $(s,t)$-path in $G$ that contains a move in $\textsc{Zigzag,
Backward},$ or Forward-D. Then $|\pi|-|\pi^{*}|=\Omega(r_{O}^{2/3}c^{-130})$.

###### Proof.

Note that for every move $m$ in the move decomposition of $\pi$,
$\widehat{\Delta}(m)\geq 0$. Moreover, since $\pi$ has a move $m^{\prime}$ in
$\textsc{Zigzag, Backward},$ or Forward-D,
$\widehat{\Delta}(m^{\prime})=\Omega(r_{O}^{2/3}c^{-130})$ by Proposition 9.
Then by Proposition 3, $|\pi|-|\pi^{*}|=\Omega(r_{O}^{2/3}c^{-130})$. ∎

######  Lemma 18.

Let $\pi$ be an $(s,t)$-path in $G$ with moves only in Stationary or Forward-S
that takes a subdivided path not in $\pi^{*}$. Then
$|\pi|-|\pi^{*}|=\Omega(r_{O}^{2/3}c^{-111})$.

###### Proof.

It will be useful to split the edges in $\pi$ and $\pi^{*}$ into two
categories, the edges in the inner graph and the edges in the outer graph. Let
$\ell_{I}^{\pi}$ and $\ell_{O}^{\pi}$ denote the number of edges in the inner
graph (respectively outer graph) in $\pi$, so
$|\pi|=\ell_{I}^{\pi}+\ell_{O}^{\pi}$. Define $\ell_{I}^{\pi^{*}}$ and
$\ell_{O}^{\pi^{*}}$ similarly. Now since $\pi$ takes a subdivided path not in
$\pi^{*}$, by part 5 of Lemma 9 we know that $\pi$ takes at least one more
subdivided path than $\pi^{*}$, so $\ell_{O}^{\pi}-\ell_{O}^{\pi^{*}}\geq z$,
where $z$ is the length of a subdivided path in $G$. Additionally, by our
amortized analysis, we know that $|\pi|-|\pi^{*}|\geq 0$. However, we claim
that our amortized analysis proves the stronger statement that
$\ell_{I}^{\pi}-\ell_{I}^{\pi^{*}}\geq 0$.

Let $m_{1},m_{2},\dots,m_{k}$ be the move decomposition of $\pi$. For
$i\in[1,k]$, let $m_{i}^{I}$ denote the restriction of move $m_{i}$ to inner
graph copy $G_{I}^{(i)}$. Note that $\sum_{i}|m_{i}^{I}|=\ell_{I}^{\pi}$. We
now define an amortized inner graph move length difference function
$\widehat{\Delta}_{I}(m_{i})$ for moves $m_{i}$, $i\in[1,k]$. If $m_{i}$ is a
move in Stationary, then let
$\widehat{\Delta}_{I}(m_{i})=|m_{i}^{I}|-(\Phi(s_{i+1})-\Phi(s_{i}))$.
Likewise, if $m_{i}$ is a move in Forward-S, then let
$\widehat{\Delta}_{I}(m_{i})=|m_{i}^{I}|-|\pi_{I}^{s^{*},t^{*}}|-(\Phi(s_{i+1})-\Phi(s_{i}))$.

Suppose that $\pi$ contains $q\in[1,k]$ moves in Forward-S. Now note that
every move in Forward-S can be interpreted as travelling on an edge in
$G_{O}$. Additionally, path $\pi^{*}$ is composed exclusively of moves in
Forward-S. Then by the unique shortest path property of $G_{O}$ (part 5 of
Lemma 9), path $\pi^{*}$ has at most $q$ moves, so $\ell_{I}^{\pi^{*}}\leq
q\cdot|\pi_{I}^{s^{*},t^{*}}|$. It follows that

$\sum_{i}\widehat{\Delta}_{I}(m_{i})=\sum_{i}|m_{i}^{I}|-q\cdot|\pi_{I}^{s^{*},t^{*}}|-(\Phi(t)-\Phi(s))=\ell_{I}^{\pi}-q\cdot|\pi_{I}^{s^{*},t^{*}}|\leq\ell_{I}^{\pi}-\ell_{I}^{\pi^{*}}$

Additionally, observe that the proofs of Lemma 14 and Lemma 16 establish that
$\widehat{\Delta}_{I}(m_{i})\geq 0$ if $m_{i}$ is in Stationary or Forward-S.
Then it immediately follows that
$\ell_{I}^{\pi}-\ell_{I}^{\pi^{*}}\geq\sum_{i}\widehat{\Delta}_{I}(m_{i})\geq
0$. Consequently,
$|\pi|-|\pi^{*}|=(\ell_{I}^{\pi}+\ell_{O}^{\pi})-(\ell_{I}^{\pi^{*}}+\ell_{O}^{\pi^{*}})\geq
z=\Omega(r_{O}^{2/3}c^{-111})$. ∎

The following lemma is immediate from Lemma 17 and Lemma 18.

######  Lemma 19.

Let $\pi$ be an $(s,t)$-path in $G$ that takes a subdivided path not in
$\pi^{*}$. Then $|\pi|-|\pi^{*}|=\Omega(r_{O}^{2/3}c^{-130})$.

We can now prove our main result.

######  Theorem 5.

For any sufficiently large parameter $c_{0}$, there are infinitely many $n$
for which there is an $n$-vertex graph $G$ such that any spanner of $G$ with
at most $c_{0}n$ edges has additive distortion $+\Omega(n^{1/7}c_{0}^{-80})$.

###### Proof.

We are given a sufficiently large parameter $c_{0}>0$. Then we will choose
construction parameter $c=\Theta(c_{0})$ for our infinite family of graphs
$G$. Recall that by Lemma 10, every graph in our family on $n$ nodes has
$m=\Theta(cn)$ edges. We choose $c$ to be sufficiently large so that for every
graph $G$ on $n$ vertices and $m$ edges in our family, $\frac{c_{0}n}{m}<1/2$.
Now consider any spanner $H$ of graph $G$ with at most $c_{0}n$ edges. Graph
$H$ will contain at most half of the edges of $G$. Then because the canonical
paths of $G$ are a partition of the edges of $G$, some canonical $(s,t)$-path
$\pi^{*}$ has at most half of its edges in $H$, for some $(s,t)\in P$.

Now fix a shortest $(s,t)$-path $\pi$ in $H$. If path $\pi$ takes a subdivided
path in $G$ not in path $\pi^{*}$, then by Lemma 19,
$|\pi|-|\pi^{*}|=\Omega(r_{O}^{2/3}c^{-130})$. Else, path $\pi$ travels
through exactly the inner graph copies that path $\pi^{*}$ travels through.
Moreover, all the subdivided paths of $\pi^{*}$ must be in $H$. Then at least
half of the inner graph subpaths of $\pi^{*}$ are missing an edge in $H$. Now
fix an inner graph copy $G_{I}$ that $\pi$ and $\pi^{*}$ pass through in $G$,
and let $\pi_{I}$ and $\pi_{I}^{*}$ be the subpaths of these paths restricted
to graph $G_{I}$. Recall that $\pi_{I}^{*}$ is a unique shortest path between
its endpoints in $G_{I}$. Then if path $\pi_{I}^{*}$ is missing an edge in
$H$, then $\pi_{I}\neq\pi_{I}^{*}$, so $|\pi_{I}|-|\pi_{I}^{*}|\geq 1$.
Finally, observe that paths $\pi^{*}$ and $\pi$ pass through
$\Omega(n_{O}^{1/2}r_{O}^{-1})$ inner graphs. It follows that
$|\pi|-|\pi^{*}|=\Omega(n_{O}^{1/2}r_{O}^{-1})$.

Then balancing our parameters so that
$r_{O}^{2/3}c^{-130}=\Theta(n_{O}^{1/2}r_{O}^{-1})$ gives us
$r_{O}=\Theta(n_{O}^{3/10}c^{78})$. We note that $r_{O}\leq\frac{x_{O}}{4}$,
so our construction requirements are satisfied. By Lemma 4, $G$ will have
$n=\Theta(n_{O}\cdot r_{O}^{4/3}c^{-116})=\Theta(n_{O}^{7/5}c^{-12})$
vertices. By the argument in the previous paragraph,
$|\pi|-|\pi^{*}|=\Omega(n_{O}^{1/5}c^{-78})=\Omega(n^{1/7}c^{-80})$. So $H$
will have additive distortion of at least $+\Omega(n^{1/7}c_{0}^{-80})$. ∎

By choosing a different value for $r_{O}$, we are able to obtain new lower
bounds against pairwise additive spanners.

######  Theorem 6.

For any sufficiently large parameter $c_{0}$, there are infinitely many $n$
for which there is an $n$-vertex graph $G$ and a set $P$ of
$p=\Theta_{c_{0}}(n^{1/2})$ demand pairs such that any pairwise spanner of
$(G,P)$ with at most $c_{0}n$ edges has additive distortion $+c_{0}$.

###### Proof.

Given $c_{0}>0$, we choose construction parameter $c=\Theta(c_{0})$ so that
for every graph $G$ on $n$ vertices and $m$ edges in our infinite family of
graphs, $\frac{c_{0}n}{m}<1/2$. We define our demand pairs to be the set of
critical pairs $P$ in our construction. Let $H$ be a pairwise spanner of
$(G,P)$ with at most $c_{0}n$ edges. By an argument identical to that of
Theorem 5, it follows that $H$ has additive distortion at least
$+k=\min\\{r_{O}^{2/3}c^{-130},n_{O}^{1/2}r_{O}^{-1}\\}$.

Now instead of choosing $r_{O}$ to grow polynomially with $n$ as in Theorem 5,
we will let $r_{O}=\Theta_{c_{0}}(1)$. Moreover, we will require that
$r_{O}>c_{0}^{300}$. Note that there exists infinitely many valid choices of
$r_{O}$ satisfying these criteria. Then for sufficiently large $c_{0}$ and
sufficiently large $n$ relative to $c_{0}$, it follows that
$+k=\min\\{r_{O}^{2/3}c^{-130},n_{O}^{1/2}r_{O}^{-1}\\}\geq c_{0}$.
Additionally, by Lemma 10, $|P|=\Theta(r_{O}^{5/3}\cdot c^{-5}\cdot
n_{O}^{1/2})=\Theta_{c_{0}}(n_{O}^{1/2})$, and $n=\Theta(n_{O}\cdot
r_{O}^{4/3}c^{-116})=\Theta_{c_{0}}(n_{O})$, so we conclude that
$|P|=\Theta_{c_{0}}(n^{1/2})$. ∎

## Acknowledgements

The authors would like to thank Shang-En Huang for helpful discussions about
lower bound graphs.

## References

  * [1] Amir Abboud and Greg Bodwin.  Error amplification for pairwise spanner lower bounds.  In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 841–854. SIAM, 2016.
  * [2] Amir Abboud and Greg Bodwin.  Error amplification for pairwise spanner lower bounds.  In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 841–854. Society for Industrial and Applied Mathematics, 2016.
  * [3] Amir Abboud and Greg Bodwin.  The 4/3 additive spanner exponent is tight.  Journal of the ACM (JACM), 64(4):28:1–28:14, 2017.
  * [4] Amir Abboud, Greg Bodwin, and Seth Pettie.  A hierarchy of lower bounds for sublinear additive spanners.  In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 568–576. Society for Industrial and Applied Mathematics, 2017.
  * [5] Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen Kobourov, and Richard Spence.  Graph spanners: A tutorial review.  Computer Science Review, 37:100253, 2020.
  * [6] Donald Aingworth, Chandra Chekuri, Piotr Indyk, and Rajeev Motwani.  Fast estimation of diameter and shortest paths (without matrix multiplication).  SIAM Journal on Computing, 28(4):1167–1181, 1999.
  * [7] Bandar Al-Dhalaan.  Fast construction of 4-additive spanners.  arXiv preprint arXiv:2106.07152, 2021.
  * [8] Noga Alon.  Testing subgraphs in large graphs.  Random Structures & Algorithms, 21(3-4):359–370, 2002.
  * [9] Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares.  On sparse spanners of weighted graphs.  Discrete & Computational Geometry, 9(1):81–100, 1993.
  * [10] Baruch Awerbuch.  Complexity of network synchronization.  Journal of the ACM (JACM), 32(4):804–823, 1985.
  * [11] Antal Balog and Imre Bárány.  On the convex hull of the integer points in a disc.  In Proceedings of the Seventh Annual Symposium on Computational Geometry, pages 162–165, 1991.
  * [12] Imre Bárány and David G Larman.  The convex hull of the integer points in a large ball.  Mathematische Annalen, 312(1):167–181, 1998.
  * [13] Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie.  Additive spanners and ($\alpha$, $\beta$)-spanners.  ACM Transactions on Algorithms (TALG), 7(1):5, 2010.
  * [14] Sandeep Bhatt, Fan Chung, Tom Leighton, and Arnold Rosenberg.  Optimal simulations of tree machines.  In 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), pages 274–282. IEEE, 1986.
  * [15] Greg Bodwin.  New results on linear size distance preservers.  SIAM Journal on Computing, 50(2):662–673, 2021.
  * [16] Greg Bodwin and Virginia Vassilevska Williams.  Very sparse additive spanners and emulators.  In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (ITCS), pages 377–382. ACM, 2015.
  * [17] Greg Bodwin and Virginia Vassilevska Williams.  Better distance preservers and additive spanners.  In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 855–872. Society for Industrial and Applied Mathematics, 2016.
  * [18] Béla Bollobás, Don Coppersmith, and Michael Elkin.  Sparse distance preservers and additive spanners.  SIAM Journal on Discrete Mathematics, 19(4):1029–1055, 2005.
  * [19] Leizhen Cai.  Np-completeness of minimum spanner problems.  Discrete Applied Mathematics, 48(2):187–194, 1994.
  * [20] Shiri Chechik.  New additive spanners.  In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 498–512. SIAM, 2013.
  * [21] Jason Cong, Andrew B Kahng, Gabriel Robins, Majid Sarrafzadeh, and CK Wong.  Performance-driven global routing for cell based IC’s.  University of California (Los Angeles). Computer Science Department, 1990\.
  * [22] Jason Cong, Andrew B Kahng, Gabriel Robins, Majid Sarrafzadeh, and CK Wong.  Provably good algorithms for performance-driven global routing.  Proc. of 5th ISCAS, pages 2240–2243, 1992.
  * [23] Don Coppersmith and Michael Elkin.  Sparse sourcewise and pairwise distance preservers.  SIAM Journal on Discrete Mathematics, 20(2):463–501, 2006.
  * [24] Marek Cygan, Fabrizio Grandoni, and Telikepalli Kavitha.  On pairwise spanners.  In 30th International Symposium on Theoretical Aspects of Computer Science, page 209, 2013.
  * [25] Michael Elkin and David Peleg.  (1+$\varepsilon$,$\beta$)-spanner constructions for general graphs.  SIAM Journal on Computing, 33(3):608–631, 2004.
  * [26] William Hesse.  Directed graphs requiring large numbers of shortcuts.  In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, pages 665–669. Society for Industrial and Applied Mathematics, 2003.
  * [27] Shang-En Huang and Seth Pettie.  Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing shortcuts.  In David Eppstein, editor, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), volume 101 of Leibniz International Proceedings in Informatics (LIPIcs), pages 26:1–26:12, Dagstuhl, Germany, 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [28] Telikepalli Kavitha.  New pairwise spanners.  Theory of Computing Systems, 61(4):1011–1036, 2017.
  * [29] Telikepalli Kavitha and Nithin M Varma.  Small stretch pairwise spanners.  In International Colloquium on Automata, Languages, and Programming, pages 601–612. Springer, 2013.
  * [30] Telikepalli Kavitha and Nithin M. Varma.  Small stretch pairwise spanners and approximate $d$-preservers.  SIAM Journal on Discrete Mathematics, 29(4):2239–2254, 2015.
  * [31] Mathias Bæk Tejs Knudsen.  Additive spanners: A simple construction.  In Scandinavian Workshop on Algorithm Theory, pages 277–281. Springer, 2014.
  * [32] Arthur L Liestman and Thomas C Shermer.  Additive spanners for hypercubes.  Parallel Processing Letters, 1(01):35–42, 1991.
  * [33] Kevin Lu.  New methods for approximating shortest paths.  PhD thesis, Massachusetts Institute of Technology, 2019.
  * [34] Kevin Lu, Virginia Vassilevska Williams, Nicole Wein, and Zixuan Xu.  Better lower bounds for shortcut sets and additive spanners via an improved alternation product.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3311–3331. SIAM, 2022.
  * [35] David Peleg and Jeffrey Ullman.  An optimal synchronizer for the hypercube.  SIAM Journal on Computing (SICOMP), 18(4):740––747, 1989.
  * [36] David Peleg and Eli Upfal.  A trade-off between space and efficiency for routing tables.  Journal of the ACM (JACM), 36(3):510–530, 1989.
  * [37] Seth Pettie.  Low distortion spanners.  ACM Transactions on Algorithms (TALG), 6(1):7, 2009.
  * [38] F Sibel Salman, Joseph Cheriyan, Ramamoorthi Ravi, and Sairam Subramanian.  Approximating the single-sink link-installation problem in network design.  SIAM Journal on Optimization, 11(3):595–610, 2001.
  * [39] Mikkel Thorup and Uri Zwick.  Spanners and emulators with sublinear distance errors.  In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 802–809. Society for Industrial and Applied Mathematics, 2006.
  * [40] David P Woodruff.  Lower bounds for additive spanners, emulators, and more.  In Foundations of Computer Science, 2006. FOCS’06. 47th Annual IEEE Symposium on, pages 389–398. IEEE, 2006.
  * [41] David P Woodruff.  Additive spanners in nearly quadratic time.  In International Colloquium on Automata, Languages, and Programming, pages 463–474. Springer, 2010.

##  Appendix A Proof of Lemma 7

Our proof of Lemma 7 begins with a result of Balog and Bárány which we restate
in our specific context below:

######  Lemma 20 ([11], Theorem 1).

For $r\geq 0$, there exists a strongly convex set $W(r)$ of integer vectors in
$\mathbb{Z}^{2}$ of size $|W(r)|=\Theta(r^{2/3})$ such that for all
$\vec{v}\in W(r)$, $r-r^{-1/3}\leq\|\vec{v}\|\leq r$.

The fact that all vectors $\vec{v}\in W(r)$ satisfy
$r-r^{-1/3}\leq\|\vec{v}\|\leq r$ is not stated explicitly in [11]. However,
it follows directly from the lower bound argument in Section 3 of [11],
specifically the assignment of parameter $\Delta$. The fact that $W(r)$ is
_strongly_ convex is also technically not stated in [11], but it follows
immediately from symmetry of the construction; that is, if $\vec{v}\in W(r)$
then $-\vec{v}\in W(r)$. We will now remove some of the vectors from the
strongly convex set $W(r)$ from Lemma 20 in order to obtain a strongly convex
set satisfying Lemma 7. Note that any subset of $W(r)$ will be a strongly
convex set satisfying property 1 of Lemma 7, so it remains to obtain the
latter two properties.

#### Property 2.

Next, we try to enforce the second property of Lemma 7: for any circular
sector $S$ with inner angle $\psi$, there are only $O(\psi\cdot r^{2/3})$
vectors in $W(r)\cap S$. To do so: restrict $W(r)$ to be the vectors in just
one quadrant of $\mathbb{R}^{2}$ (throwing away a constant fraction of these
vectors), and let $\vec{v_{1}},\vec{v_{2}},\dots,\vec{v_{k}}$ be the vectors
in $W(r)$ ordered counterclockwise about the origin. Let
$\vec{u_{i}}=\vec{v}_{i+1}-\vec{v_{i}}$ for $i\in[1,k]$ (where indices are
taken mod $k$). Observe that $\vec{u_{i}}\neq\vec{u_{j}}$ for all $i\neq j$ by
the convexity of $W(r)$. Moreover, by integrality of the vectors in $W(r)$, we
have that all $\vec{u_{i}}$ have integer coordinates. Now observe that there
are only $4(\ell+1)$ distinct integer vectors $(x,y)$ such that
$|x|+|y|=\ell$, namely, the vectors

$(i,\ell-i),(-i,\ell-i),(i,-(\ell-i)),(-i,-(\ell-i))\qquad\text{for
}i\in[0,\ell].$

Thus, the number of these vectors $\vec{u}_{i}$ of magnitude
$\|\vec{u}_{i}\|\leq m$ is at most

$\sum_{\ell=0}^{m}4(\ell+1)\leq 8m^{2}.$

We will throw away the vectors $\vec{v_{i}}$ in $W(r)$ that are close
together. Let $|W(r)|\geq\alpha r^{2/3}$ where $\alpha>0$ is some constant. We
define $W^{\prime}(r)$ as follows:

$W^{\prime}(r)=\left\\{\vec{v}_{i}\in
W(r)\mid\|\vec{u_{i}}\|>\frac{\alpha^{1/2}}{4}\cdot r^{1/3}\right\\}$

Since each $\vec{u_{i}}$ is a distinct integer vector, by our previous
observations there can be no more than $\alpha/2\cdot r^{2/3}$ vectors
$\vec{u_{i}}$ with magnitude $\|\vec{u_{i}}\|\leq\alpha^{1/2}/4\cdot r^{1/3}$.
Thus

$\left|W^{\prime}(r)\right|\geq\frac{\alpha}{2}\cdot r^{2/3}$

as desired. Now we claim that $W^{\prime}(r)$ has property 2. For notational
convenience, we will redefine $\vec{v}_{1},\dots,\vec{v}_{k}$ and vectors
$\\{\vec{u}_{i}\\}$ as before, over the _surviving_ vectors in
$W^{\prime}(r)$. Since all vectors in $W^{\prime}(r)$ lie in the same quadrant
of $\mathbb{R}^{2}$, all vectors $\\{\vec{u}_{i}\\}$ have the same signs for
their respective coordinates, and it follows that for all $i$ we have

$\|\vec{u_{i}}\|>\frac{\alpha^{1/2}}{4}\cdot r^{1/3}.$

Let $S$ be a circular sector with inner angle $\psi$, and let
$\vec{v}_{i},\vec{v}_{i+1},\dots,\vec{v}_{i+j}$ be the $j+1$ vectors in
$W^{\prime}(r)\cap S$. Now consider the convex hull
$CH(\vec{v_{i}},\dots,\vec{v}_{i+j})$ of the endpoints of vectors
$\vec{v_{i}},\dots,\vec{v}_{i+j}$. Observe that the boundary of this convex
hull has length

$\sum_{\nu=i}^{i+j-1}\|\vec{u}_{\nu}\|+\|\vec{v}_{i+j}-\vec{v}_{i}\|.$

Furthermore, if $a_{S}$ denotes the circular arc of radius $r$ spanning the
circular sector $S$, then the convex hull
$CH(a_{S},\vec{v_{i}},\vec{v}_{i+j})$ encloses
$CH(\vec{v_{i}},\dots,\vec{v}_{i+j})$. The length of the boundary of
$CH(a_{S},\vec{v_{i}},\vec{v}_{i+j})$ is dominated by the arc $a_{S}$, so it
is $O(r\psi)$. We thus have

$\displaystyle\Omega\left(j\cdot
r^{1/3}\right)\leq\sum_{\nu=i}^{i+j-1}\|\vec{u}_{\nu}\|+\|\vec{v}_{i+j}-\vec{v}_{i}\|\leq
O(r\psi)$

so we conclude that $j\leq O\left(\psi\cdot r^{2/3}\right)$.

#### Property 3.

Lastly, we enforce the property that for each vector $\vec{v}$, the vector in
our strongly convex set with the largest magnitude scalar projection onto
$\vec{v}$ is $\vec{v}$ itself. To do so, we will pass from $W^{\prime}(r)$ to
$W^{\prime\prime}(r)$. Note that any subset of $W^{\prime}(r)$ will be a
strongly convex set and satisfy properties 1 and 2 of Lemma 7.

First we overview our strategy to construct $W^{\prime\prime}(r)$. We
repeatedly select some $\vec{v}\in W^{\prime}(r)$ and add it to
$W^{\prime\prime}(r)$. Let $\ell_{v}$ be the chord of the circle of radius $r$
that intersects the endpoint of $\vec{v}$ and is perpendicular to it. If there
are vectors $\vec{u}\in W^{\prime}(r)$ with scalar projection
$\texttt{proj}_{\vec{v}}\vec{u}\geq\|\vec{v}\|$, then they lie on the side of
$\ell_{v}$ opposite the origin. We throw away all such vectors from
$W^{\prime}(r)$ before proceeding, and selecting one of the surviving vectors
in $W^{\prime}(r)$ as our next choice of $\vec{v}$.

Let us bound the total number of vectors discarded in this way. Using the fact
that $r-r^{-1/3}\leq\|\vec{v}\|\leq r$, a straightforward application of the
Pythagorean theorem shows that the chord $\ell_{v}$ has length $O(r^{1/3})$.
Thus, the angle $\psi_{v}$ of the circular sector spanning $\ell_{v}$
satisfies $\sin(\psi_{v})=O(r^{-2/3})$, and thus $\psi_{v}=O(r^{-2/3})$.
Applying property $2$ of Lemma 7, this circular sector contains only $O(1)$
vectors from $W^{\prime}(r)$. Thus, we discard only $O(1)$ vectors from
$W^{\prime}(r)$ for each vector that we add to $W^{\prime\prime}(r)$, and so
we discard only a constant fraction of the vectors in $W^{\prime}(r)$ in
total.

So far, this construction guarantees that, for any vector $\vec{v}$ added to
$W^{\prime\prime}(r)$, no _future_ vector $\vec{v}^{\prime}$ added to
$W^{\prime\prime}(r)$ has larger projection onto $\vec{v}$ than $\vec{v}$
itself. We still need to handle the opposite dependency, in which a _past_
vector $\vec{v}^{\prime}$ added to $W^{\prime\prime}(r)$ has larger projection
onto $\vec{v}$ than $\vec{v}$ itself. In fact, this is easily handled by
considering the vectors in $W^{\prime}(r)$ in a specific order, rather than
choosing an arbitrary $\vec{v}\in W^{\prime}(r)$ in each round. Notice that
this problematic dependence only occurs in the case when
$\|\vec{v}^{\prime}\|>\|\vec{v}\|$, and so $\vec{v}$ escapes the discarded
sector for $\vec{v}^{\prime}$, but $\vec{v}^{\prime}$ lies in the discarded
sector for $\vec{v}$. We therefore select the vector $\vec{v}\in
W^{\prime}(r)$ with _minimum length_ $\|\vec{v}\|$ in each round (breaking
ties arbitrarily). This avoid conflicts as described, since we would then
consider $\vec{v}$ first, and discard $\vec{v}^{\prime}$.

##  Appendix B Proof of Proposition 12

We must show that any optimal solution to our relaxed optimization problem is
of form
$\delta_{1}^{\prime}=w_{\vec{q}_{1}}\cdot(q_{1})_{y}+w_{\vec{q}_{2}}\cdot(q_{2})_{y}$,
where $\vec{q}_{1}=((q_{1})_{x},(q_{1})_{y})\in Q_{1}$,
$\vec{q}_{2}=((q_{2})_{x},(q_{2})_{y})\in Q_{2}$, and
$w_{\vec{q}_{1}}\cdot(q_{1})_{x}+w_{\vec{q}_{2}}\cdot(q_{2})_{x}=v_{x}-u_{x}$.
We can accomplish this by showing that any feasible solution in general form
can be converted into a feasible solution in our desired form that is at least
as good.

We first show that there is at most one $w_{\vec{q}_{1}}>0$ where
$\vec{q}_{1}\in Q_{1}$ in any optimal solution. Corresponding to the vectors
in $Q_{1}$, we define the following function $f$. For all $1-i^{*}\leq x\leq
c-i^{*}$, let

$f(x)=-1/2\cdot((x+i^{*})(x+i^{*}-1)-i^{*}(i^{*}-1)).$

Note that for all $\vec{q}=(q_{x},q_{y})\in Q_{1}$, $f(q_{x})=q_{y}$.
Moreover, function $f$ is concave over its domain and strictly decreasing.

######  Proposition 16.

Let $\\{w_{\vec{q}}\\}_{\vec{q}\in Q_{1}\cup Q_{2}}$ be a feasible solution to
LP1. Then we can obtain a feasible solution
$\\{w^{\prime}_{\vec{q}}\\}_{\vec{q}\in Q_{1}\cup Q_{2}}$ that is at least as
good as $\\{w_{\vec{q}}\\}$, by letting

$\displaystyle w^{\prime}_{(x,f(x))}$ $\displaystyle:=0$ for
$\displaystyle\quad x\in[1-i^{*},-2]$ $\displaystyle w^{\prime}_{(-1,f(-1))}$
$\displaystyle:=-\sum_{x\in[1-i^{*},-1]}x\cdot w_{(x,f(x))}$ $\displaystyle
w^{\prime}_{(0,f(0))}$ $\displaystyle:=0$ $\displaystyle
w^{\prime}_{(1,f(1))}$ $\displaystyle:=\sum_{x\in[1,c-i^{*}]}x\cdot
w_{(x,f(x))}$ $\displaystyle w^{\prime}_{(x,f(x))}$ $\displaystyle:=0$ for
$\displaystyle\quad x\in[2,c-i^{*}]$ $\displaystyle w^{\prime}_{\vec{q}}$
$\displaystyle:=w_{\vec{q}}$ for $\displaystyle\quad\vec{q}\in Q_{2}$

###### Proof.

  * •

Feasible: We must verify that $w_{\vec{q}}\geq 0$ for all $\vec{q}\in
Q_{1}\cup Q_{2}$ as required. This follows straightforwardly from the
definition of our solution and the fact that $w_{\vec{q}}\geq 0$ for all
$\vec{q}\in Q_{1}\cup Q_{2}$, since we assumed our initial solution was
feasible.

Additionally, the constraint $\sum_{\vec{q}\in Q_{1}\cup