University of Warwick,
UKS.Coy@warwick.ac.ukhttps://orcid.org/0000-0001-8500-8690Research supported
in part by the Centre for Discrete Mathematics and its Applications (DIMAP)
and an EPSRC studentship. University of Warwick,
UKA.Czumaj@warwick.ac.ukhttps://orcid.org/0000-0002-7743-438XResearch
supported in part by the Centre for Discrete Mathematics and its Applications
(DIMAP), EPSRC award EP/V01305X/1, and the Simons Foundation Award No. 663281
granted to the Institute of Mathematics of the Polish Academy of Sciences for
the years 2021–2023. University of Paderborn,
Germanyscheideler@upb.dehttps://orcid.org/0000-0002-5278-528XThis work was
partially supported by the German Research Foundation (DFG) within the
Collaborative Research Centre _On-The-Fly Computing (GZ: SFB 901/3)_ under the
project number 160364472 University of Freiburg,
<EMAIL_ADDRESS>freiburg.dehttps://orcid.org/0000-0001-9660-1270 University of Paderborn,
Germanyjwerth@mail.upb.dehttps://orcid.org/0000-0002-5110-5625This work was
partially supported by the German Research Foundation (DFG) within the
Collaborative Research Centre _On-The-Fly Computing (GZ: SFB 901/3)_ under the
project number 160364472 Sam Coy and Artur Czumaj and Christian Scheideler and
Philipp Schneider and Julian Werthmann

###### Acknowledgements.

We would like to thank Martijn Struijs for valuable discussions concerning the
geometric insights of the paper. Any errors remain our own. <ccs2012>
<concept> <concept_id>10003752.10003809.10010172</concept_id>
<concept_desc>Theory of computation Distributed algorithms</concept_desc>
<concept_significance>500</concept_significance> </concept> </ccs2012>
[500]Theory of computation Distributed algorithms

# Routing Schemes for Hybrid Communication Networks

Sam Coy  Artur Czumaj  Christian Scheideler  Philipp Schneider  Julian
Werthmann

###### Abstract

Hybrid communication networks provide multiple modes of communication with
varying characteristics. The $\mathsf{HYBRID}$ model was introduced to allow
theoretical study of such networks. It combines a _local_ mode, which
restricts communication among nodes to a given graph and a _global_ mode where
any two nodes may communicate in principle, but only very little such
communication can take place per unit of time. For an example consider an ad-
hoc wifi network among mobile devices supplemented with comparatively limited
communication via the cellular network.
We consider the problem of the computation of _routing schemes_ , where nodes
have to compute small labels and routing tables that allow for efficient
routing of messages in the local network, which typically offers the majority
of the throughput. Recent work has shown that using the $\mathsf{HYBRID}$
model admits a significant speed-up compared to what would be possible if
either communication mode were used in isolation. Nonetheless, if general
graphs are used as local graph the computation of routing schemes still takes
polynomial rounds in the $\mathsf{HYBRID}$ model.
We bypass this lower bound by restricting the local graph to unit-disc-graphs
with few “radio holes” and solve the problem deterministically with running
time, label size, and size of routing tables all in
$O(|\mathcal{H}|^{2}\\!+\\!\log n)$ where $|\mathcal{H}|$ is the number of
such radio holes. Our work builds on that of [Coy et al., OPODIS’21], which
obtains this result if no radio holes are present thus making the graph much
simpler (topologically similar to a tree). We develop new techniques to
achieve this, a decomposition of the local graph into path-convex regions,
where each region contains a shortest path for any pair of nodes in it. We
continue to investigate properties of shortest paths algorithms on grid
graphs, which can be utilized as simpler representations of unit-disc-graphs.

###### keywords:

Hybrid networks, overlay networks, unit-disk graphs, routing schemes

inline, color=yellow!50]Julian: We need to remember to add an acknowledgement
for Martijn

##  1 Introduction

The $\mathsf{HYBRID}$ model was introduced in [4] as a means to study
distributed systems which leverage multiple communication modes of different
characteristics. Of particular interest are networks that combine a _local_
communication mode, which has a large bandwidth but is restricted to edges of
a _graph_ on the nodes of the network, with a _global_ communication mode
where any two nodes may communicate in principle, but very little such
communication can take place per unit of time. This concept captures various
real distributed systems, notably networks of cellphones that combine high
bandwidth but locally restricted wireless communication on a _unit-disc-graph_
with data transmission via the cellular network.

_Routing Schemes_ are one of the most fundamental distributed data structures,
most prominently employed in the Internet, and are used to forward packets
among connected nodes in a network in order to facilitate data exchange
between any pairs of nodes. In the distributed variant of the problem the
nodes initially only know their incident neighbors in the network and need to
communicate as efficiently as possible using their available means of
communication such that subsequently each node knows its label and a routing
table with the following properties. Given a packet with the label of the
receiver node in the header, any node must be able to forward this packet in
the network using the label and its routing table such that the packet
eventually reaches the intended receiver. Algorithms for routing schemes in
hybrid networks are of increasing importance, as contemporary communication
standards support such settings, one prominent example being the 5G standard
[2]. Formally we define routing schemes as follows.

######  Definition 1.1 (Routing Schemes).

A routing scheme on a connected graph $G=(V,E)$ consists of labels
$\lambda(v)$ and routing functions (aka routing table) $\rho_{v}$ for each
$v\in V$. $\rho_{v}$ maps labels to neighbors of $v$ in $G$, such that the
following holds. Let $s,t\in V$. Let $v_{0}=s$ and
$v_{i+1}=\rho_{v_{i}}(\lambda(t))$ for $i\geq 1$. Then there is an
$\ell\in\mathbb{N}$, such that $v_{\ell}=t$. A routing scheme is an
approximation with _stretch_ $\alpha$ if
$\ell_{st}\leq\alpha\cdot\operatorname{\,hop}(s,t)$ for all $s,t\in V$, where
$\operatorname{\,hop}(s,t)$ is smallest number of edges of any $st$-path, and
$\ell_{st}$ is the length of the induced routing path from $s$ to $t$.111Note
that minimizing hop-distance in a unit-disc-graph essentially minimizes the
Euclidean distance that the path covers, thus graph weights are not required.
This is due to the fact that there is always a shortest path $\Pi$ that covers
distance at least 1 with every two hops. Thus, if $d_{G}(\Pi)$ is the distance
in the UDG measured by the euclidean length of its edges then
$d_{G}(\Pi)\leq|\Pi|\leq 2d_{G}(\Pi)$.

Since typically large amounts of packets are exchanged between senders and
receivers as part of simultaneously ongoing sessions we concentrate on routing
schemes for the local network graph, which offers much larger throughput that
than what is possible on the global network, since the latter either involves
higher costs or is more restricted as infrastructure is shared, like
communicating via the cellular network (however, we need very little local
communication to actually compute the routing scheme).

Our first goal is to optimize the round complexity of computing such a routing
scheme, which is important since frequent changes in the topology of a local
network among mobile devices necessitates its fast re-computation. The second
goal is to minimize the size of the labels and local routing tables as these
must be shared in advance (e.g. via the global network) to initiate a session
between two nodes. The third goal is to minimize the stretch of the routing
path between sender and receiver, minimizing latency and alleviating
congestion.

We consider the above problem in the $\mathsf{HYBRID}$ model of computing that
has received increasing attention during the last few years [4, 14, 12, 7, 8,
1, 15, 9]. Formally, the $\mathsf{HYBRID}$ model builds on the classic
principle of synchronous message passing:

######  Definition 1.2 (Synchronous message passing, cf. [21]).

We have $n$ computational nodes with some initial state and unique identifiers
(IDs) in $[n]:=\\{1,\dots,n\\}$. Time is slotted into discrete rounds. In each
round, nodes receive messages from the previous round; they perform
(unlimited) computation based on their internal states and the messages they
received so far; and finally, based on those computations, they send messages
to other nodes in the network.

Note that the synchronous message passing model focuses on the analysis of
round complexity of a distributed problem (the number of rounds required to
solve it). The $\mathsf{HYBRID}$ model restricts which nodes may communicate
in a given round and to what extent.

######  Definition 1.3 ($\mathsf{HYBRID}$ model, cf. [4]).

The _local_ communication mode is modeled as a connected graph, in which each
node is initially aware of its neighbors and is allowed to send a message of
size $\lambda$ bits to each neighbor in each round. In the _global_
communication mode, each round each node may send or receive $\gamma$ bits
to/from every other node that can be addressed with its ID in $[n]$ in case it
is known. If any restrictions are violated in a given round, we assume a
strong adversary selects the messages that are dropped.

In this paper, we consider a weak form of the $\mathsf{HYBRID}$ model, which
sets $\lambda\in\smash{O}(\log n)$ and $\gamma\in\smash{O}(\log^{2}n)$, which
corresponds to the combination of the classic distributed models
$\mathsf{CONGEST}$ 222Some previous papers that consider hybrid models use
$\lambda=\infty$, i.e., the $\mathsf{LOCAL}$ model as local mode. as local
mode, and $\mathsf{NODE\,\,CAPACITATED\,\,CLIQUE}$ ($\mathsf{NCC}$)333Our
approach works for the stricter $\mathsf{NCC_{0}}$ model where only incident
nodes in the local network and those that have been introduced can communicate
globally. as global mode.

The distributed problem of computing routing schemes on the local
communication graph is an excellent fit for the $\mathsf{HYBRID}$ model, since
the problem is known to require $\smash{\widetilde{\Omega}}(n)$ rounds of
communication (where $\smash{\widetilde{O}},\smash{\widetilde{\Omega}}$ hides
$\operatorname{polylog}n$ factors) if only _either_ communication via the
local mode _or_ the global mode is permitted, see [15]. The lower bound for
the local communication mode holds even if the input graph is a path and even
for unbounded local communication. It is natural to wonder if adding a modest
amount of global communication on top of a local network significantly
improves the required number of communication rounds to establish a routing
scheme in the network. This question was recently answered positively by [15],
where it was shown that routing schemes with small labels can be computed in
$\smash{\widetilde{O}}(n^{1/3})$ rounds for _arbitrary_ local graphs. However,
[15] also shows that a polynomial number of rounds is required to solve the
problem even approximately (in particular, an exact solution with labels up to
size $\smash{O}(n^{2/3})$ requires $\smash{\widetilde{\Omega}}(n^{1/3})$
rounds).

To mitigate this lower bound, [9] considers local communication networks that
are restricted to certain interesting classes of graphs for which they can
compute routing schemes in just $\smash{O}(\log n)$ rounds. In this article we
will continue this line of work and consider local communication graphs that
are unit-disk graphs (UDGs). Such a UDG $G=(V,E)$ satisfies the property that
nodes are embedded in the Euclidean plane and are connected iff they are at
distance at most 1 (see Def. 2.1). Note that UDGs have been extensively
studied as a model capturing how multiple devices using wireless ad-hoc
connections communicate (see, e.g., [5, 6, 9, 16, 17, 18], all of which handle
routing schemes in such UDGs).

In [9] it was shown that the nodes of a UDG can together simulate a much
simpler _grid graph_ (see Def. 2.2) structure with constant overhead in round
complexity, such that the connectivity, the hole-freeness, and the hop
distance up to a constant factor are preserved. Furthermore, [9] shows that a
routing scheme on a grid graph can efficiently be transformed into a routing
scheme for the underlying UDG, which introduces only a constant overhead on
label size and local routing information and takes only a constant number of
additional rounds.

This allows them to consider the much simpler grid graphs for the computation
of routing schemes to generate good routing schemes for UDGs. However, their
actual algorithm for computing a routing scheme for a grid graph comes with a
caveat: it works only for grid graphs _without holes_ , which, loosely
speaking, are points in the grid without nodes on them that are enclosed by a
cycle in the grid graph (more formally in Definition 2.8), which implies
routing schemes only for UDGs without “radio holes”, which roughly correspond
to areas enclosed by the UDG that are not covered by nodes (see [9] for the
formal definition of radio holes in UDGs).

In this work we extend the solution to UDGs with such radio holes. Note that
the transformations given in [9] from UDGs to grid graphs work even if there
are holes, which essentially allows us to focus on the computation routing
schemes for grid graphs with holes, which gives the same for arbitrary UDGs.
Our algorithm is asymptotically as efficient (in computation time, and label
and table sizes of the resulting routing scheme) as the algorithm of [9] if
the number of holes $|\mathcal{H}|$ is small.

We stress that it is _significantly_ more challenging to compute routing
schemes on grid graphs with such holes than on grid graphs without holes. In
the paper of Coy et al. ([9]) the authors heavily exploit the property that
any $st$-path can be deformed into any other $st$-path: this is _not true_ in
our setting. In particular, it is easy to come up with examples of grid graphs
with $|\mathcal{H}|$ holes for which there are at least $2^{|\mathcal{H}|}$
“reasonable” 444By a reasonable path we mean a path which does not completely
encircle a hole or spiral around one: such a path can clearly be shortened.
classes of $st$-paths (intuitively: paths which do not completely encircle or
spiral around holes) which cannot be deformed into each other. Worse still, we
can make all-but-one of these classes of paths almost arbitrarily long, and so
it is not the case that we can consider just one arbitrary class of $st$-paths
and obtain an approximate shortest path. Therefore we must determine the class
in which an exact shortest $st$-path lies, and this seems to require a
sparsifying structure which scales in complexity with the number of holes.

###  1.1 Contributions

Our main contribution is the following result.

######  Theorem 1.4 (Main Result for Grid Graphs).

Given a grid graph $\Gamma$ with a set $\mathcal{H}$ of holes (see Def. 2.8),
we can compute an exact routing scheme for $\Gamma$ in
$O(|\mathcal{H}|^{2}+\log n)$ rounds in the $\mathsf{HYBRID}$ model. The
labels are of size $O(\log n)$; nodes need to locally store
$O(|\mathcal{H}|^{2}\log n)$ bits.

This result acts as an extension of the result presented in Coy et al., [9],
which assumes that no holes are present making the graph structure much
simpler. Note that [9] showed that grid graphs approximate unit-disk graphs
well (we briefly summarize this in Section 2), which leads to the following
corollary:

######  Corollary 1.5 (Main Result for UDGs).

The above routing scheme can be transformed into a routing scheme which yields
constant-stretch shortest paths for unit-disk graphs. Round complexity, label
size, and local storage are asymptotically the same as above.

We believe that several of our technical contributions are of independent
interest. Our main technical contribution is a decomposition of a grid graph
into _simple, path-convex_ regions which have useful properties for routing.
We also provide a small skeleton structure of the UDG called a landmark graph
with the property that shortest paths in the landmark graph are topologically
the same (i.e., circumnavigate holes in the same way) as in the original
graph, which may be useful when solving shortest paths on grid graphs and UDGs
in $\mathsf{HYBRID}$ or for similar problems in other models of computation.
Furthermore we give an $O(\log n)$ round algorithm for solving SSSP exactly in
simple grid graphs and an $O(\log n)$ round algorithm for finding the distance
from every node in a simple grid graph to a portal.

###  1.2 Overview

For an end-to-end overview of our approach, following an example graph, see
Appendix A.

In Section 3, we give an algorithm that solves SSSP in hole-free grid graphs
(see Definition 2.2 and Definition 2.10) in $\smash{O}(\log n)$ rounds
deterministically. We create two helper graphs, one representing its
horizontal connections and one for the vertical connections, and we prove that
SSSP solutions for these two graphs suffice to solve SSSP in the original grid
graph. Further, we present a scheme that allows us to compute shortest paths
of nodes to _portal_ sets (i.e., a connected straight path in the grid graph).

In Section 4, we show that a grid graph can be decomposed into regions such
that each region is simple (contains no holes) and path-convex (for any nodes
$s,t$ in a region, a shortest $st$-path lies entirely in their region), and
with overlap only in portals (specifically called gates). We do this in
stages: we decompose the graph into simple regions; we decompose these regions
further so that they are “tunnel” shaped (i.e., bounded by at most $2$ gates);
and finally we decompose them further still to ensure they are path-convex. We
show that we can perform this decomposition quickly and the number of
resulting regions is low.

In Section 5, we give a skeleton structure on this decomposition to
facilitates routing. We mark vertices which lie on many shortest paths as
_landmarks_. We connect some landmarks in the same region to each other to
form a _landmark graph_ , and show it can be computed quickly. Finally, we
prove that for any grid nodes $s$ and $t$, a shortest $st$-path goes through
the same regions as the shortest path from a landmark near $s$ to a landmark
near $t$.

In Section 6, we combine our results to construct the routing scheme, first
showing that each node can efficiently learn the whole landmark graph. We then
show that the region which a packet should enter next can be determined by
combining information about the landmark graph, the target node’s label, and
local information about the region the message is currently in. Nodes forward
received packets to their neighbor which is closest to the packet’s next
region. We repeat this until the packet arrives at the target region,
switching then to the routing scheme of [9].

###  1.3 Related Work

Shortest Paths in Hybrid Networks. Previous work in the $\mathsf{HYBRID}$
model has mostly focused on shortest path problems [4, 14, 12, 7, 1]. In the
$k$-sources shortest path ($k$-SSP) problem, all nodes must learn their
distance in the (weighted) local network to a set of $k$ sources. Particular
focus has been given to the all-pairs (APSP, $k=n$) and single-sources (SSSP,
$k=1$) shortest-path problems. Note that solving the APSP problem gives a
solution to the routing scheme problem. The complexity of APSP is essentially
settled: [4, 14] give an algorithm taking $\smash{\widetilde{O}}(\\!\sqrt{n})$
rounds, and this matches a lower bound of
$\smash{\widetilde{\Omega}}(\\!\sqrt{k})$ to solve $k$-SSP even for polynomial
approximations. This lower bound even matches a deterministic algorithm due to
[1], although only with an approximation factor of $\smash{O}(\frac{\log
n}{\log\log n})$.555These results are in the more powerful hybrid combination
of $\mathsf{LOCAL}$ and $\mathsf{NCC}$. For $k$-SSP the
$\smash{\widetilde{\Omega}}(\\!\sqrt{k})$ lower bound has been matched by [7]
with a constant stretch algorithm, given sufficiently large $k$ (roughly
$k\in\Omega(n^{2/3})$).${}^{\ref{ftn:powerful_hybrid}}$ Whether there are any
$\smash{\widetilde{O}}(\\!\sqrt{k})$ round $k$-SSP algorithms on general
graphs for $1<k<n^{2/3}$ remains open. The state-of-the-art algorithm for
exact SSSP is provided by [7] and takes $\smash{O}(n^{1/3})$
rounds.${}^{\ref{ftn:powerful_hybrid}}$ A recent result by [22], which solves
SSSP by $\smash{\widetilde{O}}(1)$ applications of an instruction set called
“minor-aggregation” when given access to an oracle that solves the so called
Eulerian Orientation problem, can be adapted for a $(1\\!+\\!\varepsilon)$
approximation of SSSP in $\smash{\widetilde{O}}(1)$ rounds, as was shown in
[24].${}^{\ref{ftn:powerful_hybrid}}$ An exact, deterministic solution for
SSSP in $\smash{O}(\log n)$ rounds has been achieved on specific classes of
graphs (e.g. cactus graphs, which includes trees) by [12]. Another exact SSSP
algorithm that takes $\smash{\widetilde{O}}(\\!\sqrt{SPD})$ rounds (where
$SPD$ is the shortest-path-diameter of the local graph) is provided by [4].

Routing Schemes in Distributed Networks. Our work builds on [9], in which they
show how to compute a routing scheme for a UDG, by computing a routing scheme
for a corresponding grid graph (see Section 2). Their approach requires a
simplifying assumption: the grid graph needs to be free of holes (see Def.
2.8), and this imposes a similar restriction on the underlying UDG. We remove
that assumption in this work. In a recent article, [15] considers computing
routing schemes in the $\mathsf{HYBRID}$ model on general graphs: they show
that in $\smash{\widetilde{O}}(n^{1/3})$ rounds one can compute exact routing
schemes with labels of size $\smash{\widetilde{O}}(n^{2/3})$ bits, or constant
stretch approximations with smaller labels of $\smash{O}(\log n)$ bits.
Interestingly, [15] also gives lower bounds: they show that it takes
$\smash{\widetilde{\Omega}}(n^{1/3})$ rounds to compute exact routing schemes
that hold for relabelings of size $\smash{O}(n^{2/3})$ and on unweighted
graphs. They also give polynomial lower bounds for constant approximations on
weighted graphs, implying that in order to overcome this lower bound in round
complexity and label size, the restriction to a class of graphs is necessary!
The distributed round complexity of computing routing schemes was also
considered in the $\mathsf{CONGEST}$ model. In general, it takes
$\smash{\widetilde{\Omega}}(\\!\sqrt{n}+D)$ rounds to solve the problem [23]
(where $D$ is the graph diameter). This was nearly matched in a series of
algorithmic results [19, 20, 11], for example, [11] gives a solution with
stretch $\smash{O}(k)$, routing tables of size
$\smash{\widetilde{O}}(n^{1/k})$, labels of size $\smash{\widetilde{O}}(k)$ in
$\smash{O}\big{(}n^{1/2+1/k}\\!+\\!D_{G}\big{)}\cdot n^{o(1)}$ rounds.

SINR Model as Local Network. A well-accepted model for communication in
wireless networks is the Signal to Interference and Noise Ratio model, where a
message is only received if the signal strength over the distance between
sender and receiver is larger than the interference by other nodes plus some
ambient noise. The latter implies a maximum range at which messages can be
received, thus nodes that can communicate at zero interference induce a UDG. A
result of Halldórsson and Tonoyan [13] connects the SINR model to the
$\mathsf{CONGEST}$ model. They show that the SINR model allows to simulate the
$\mathsf{CONGEST}$ model on a locally sparse backbone structure which inherits
the UDG property from the SINR model. Thus, by using the SINR model as local
mode with our global mode ($\mathsf{NCC}_{0}$), we obtain a routing scheme on
the backbone. This solution can be extended to nodes outside the backbone, by
leveraging the “download” routine provided in [13].

##  2 Unit Disk Graphs and Grid Graphs

In this section we mainly introduce concepts from [9], which we require in
many of the following sections. We consider the class of _Unit Disk Graphs_
(UDG) defined as follows:

######  Definition 2.1 (Unit Disk Graphs).

$G=(V,E)$ is a UDG if each node $v\in V$ is associated with a unique point in
$\mathbb{R}^{2}$ and $u,v\in V:\\{u,v\\}\in E$ iff $\|u\\!-\\!v\|_{2}\leq 1$.

_Grid graphs_ can be seen as a sparsifying structure for UDGs which can be
easily simulated while preserving certain geometric properties and
significantly simplifying the construction of algorithms for the original UDG
(c.f., [9], more on that further below).

######  Definition 2.2 (Grid Graphs).

A _grid graph_ $\Gamma=(V_{\Gamma},E_{\Gamma})$ is a graph such that the
vertices $V$ uniquely correspond to points on a square grid $\mathbb{Z}^{2}$.
Two vertices are connected by an edge in $E_{\Gamma}$ iff their corresponding
points on the grid are horizontally or vertically adjacent.

###  2.1 Grid Graph Abstractions of Unit Disk Graphs

We further explain the correspondence between UDGs and grid graphs. As was
shown in [9], one can compute and simulate a grid-graph abstraction
$\Gamma=(V_{\Gamma},E_{\Gamma})$ of any input UDG using only local
communication in $\smash{O}(1)$ rounds. In this simulated grid graph $\Gamma$,
each grid node is represented with a close by node in the UDG. Any UDG node
has to represent only a constant number of grid nodes (and can thus simulate
all grid nodes it represents).

######  Theorem 2.3 (c.f. [9]).

Let $G=(V,E)$ be a UDG. We can compute a grid graph
$\Gamma=(V_{\Gamma},E_{\Gamma})$ in $\smash{O}(1)$ rounds, such that each grid
node $g\in V_{\Gamma}$ is represented by some node $v\in V$ with
$\|v\\!-\\!g\|_{2}\leq 1$. _Every_ node $v\in V$ has a representative $r\in V$
of some grid node $g\in V_{\Gamma}$ with $\operatorname{\,hop}_{G}(v,r)\leq
1$. A round of the $\mathsf{HYBRID}$ model on $\Gamma$ can be simulated by the
set of representatives in $V$ in $\smash{O}(1)$ rounds, and for any $s,t\in V$
with $\\{s,t\\}\notin E$ we have close-by representatives $g_{s},g_{r}\in
V_{\Gamma}$ such that from a shortest path $\Pi_{\Gamma}(g_{s},g_{t})$ from
$g_{s}$ to $g_{t}$ in $\Gamma$ we can (locally and in $\smash{O}(1)$ rounds)
construct a path $\Pi_{G}(s,t)$ in $G$ such that $|\Pi_{G}(s,t)|\leq
36\cdot\operatorname{\,dist}_{G}(s,t)$

The theorem above means that approximate paths with decent stretch on the UDG
can be constructed from shortest paths on the grid graph abstraction $\Gamma$.
In particular, this implies that any constant stretch routing scheme on
$\Gamma$ also gives a constant stretch routing scheme on the underlying UDG.
Therefore in order to obtain constant stretch routing schemes on UDGs it is
sufficient to consider the problem on the (easier) class of grid graphs.

######  Theorem 2.4 (c.f. [9]).

Any algorithm that computes routing schemes with stretch $s$, labels of at
most $x$ and local routing information at most $y$ bits on _any grid graph_ in
$z$ rounds (where $x,y,z$ depend on $n$) implies an algorithm to compute a
routing scheme with stretch $36\cdot s$ on any UDG with labels of
$\smash{O}(x)$ bits, local routing information of $\smash{O}(y)$ bits in
$\smash{O}(z)$ rounds.

###  2.2 Geometric Structure of Grid Graphs

We start by defining paths and distances in grid graphs.

######  Definition 2.5 (Paths).

Let $\Gamma=(V_{\Gamma},E_{\Gamma})$ be an grid graph. We define a path
$\Pi\subseteq E$ as a set of incident edges of $G$. For a $uv$-path $\Pi$ and
a $vw$-path $\Pi^{\prime}$ we denote the composite path from $u$ to $w$
obtained by concatenating $\Pi$ and $\Pi^{\prime}$ as $\Pi\circ\Pi^{\prime}$.
By $|\Pi|$ we denote the number of edges (or _hops_) of a path $\Pi$. However,
we will occasionally identify paths by the set of endpoints of its edges.

######  Definition 2.6 (Distances).

The _hop-distance_ between two nodes $u,v\in V$ is defined as
$d_{G}(u,v):=\\!\min_{\text{$u$-$v$-path }\Pi}|\Pi|$. Note that the hop
distance is equal to the distance as all our edges have unit weight, hence we
use the two interchangeably. Let $|\Pi_{x}|$ be the set of horizontal edges in
the grid graph. Then $d_{x,G}(u,v):=\\!\min_{\text{$u$-$v$-path
}\Pi}|\Pi_{x}|$ is the horizontal distance between $u$ and $v$. Analogously we
define the vertical distance $d_{y,G}$. We will drop the subscript $G$ when it
is clear from the context.

To analyze grid graphs we define some geometric structures, starting with
_portals_ [9].

######  Definition 2.7 (Portals).

Let $E_{v}$ be the set of vertical edges of some grid graph $\Gamma=(V,E)$.
Then the vertical portals are the connected components of the sub graph
$(V,E_{v})$. We say that portals $p_{1}$ and $p_{2}$ are _adjacent_ if $p_{1}$
is connected by an (horizontal) edge in $E$ to a node in $p_{2}$. Horizontal
portals are based on the set of horizontal edges $E_{h}$ and the corresponding
terms are defined analogously.

Next, we introduce the concept of _holes_ in a grid graph. Intuitively, the
area that is covered by a grid graph can be described by “filling in” the grid
cells (those are unit squares $[a,a\\!+\\!1]\times[b,b\\!+\\!1]$ with
$a,b\in\mathbb{Z}$) where all four corner nodes represent nodes in $\Gamma$ as
well as all edges of $\Gamma$. The holes are the connected areas in the
Euclidean plane which are not “filled”.

######  Definition 2.8.

Given a grid graph $\Gamma=(V_{\Gamma},E_{\Gamma})$. We define
$S_{\Gamma}\subseteq\mathbb{R}^{2}$ as

$\displaystyle
S_{\Gamma}^{\text{cells}}:=\\{[a,a\\!+\\!1]\\!\times\\![b,b\\!+\\!1]\mid\text{nodes
in $V_{\Gamma}$ at
$(a,b),(a\\!+\\!1,b),(a,b\\!+\\!1),(a\\!+\\!1,b\\!+\\!1)$}\\}$ $\displaystyle
S_{\Gamma}^{\text{edges}}:=\\{x\cdot u+(1\\!-\\!x)\cdot v\mid\\{u,v\\}\in
E_{\Gamma},x\in[0,1]\\}$ $\displaystyle
S_{\Gamma}:=S_{\Gamma}^{\text{cells}}\cup S_{\Gamma}^{\text{edges}}$

Then all _maximal connected components_ in the complement
$\mathbb{R}^{2}\setminus S_{\Gamma}$ constitute the set of holes induced by
$\Gamma$. We define the _set of inner holes_ $\mathcal{H}$ as all bounded,
maximal connected components in the complement $\mathbb{R}^{2}\setminus
S_{\Gamma}$. As the number of nodes in $\Gamma$ is finite, there is exactly
one maximal connected component in $\mathbb{R}^{2}\setminus S_{\Gamma}$ that
is unbounded, which we call the _outer hole_.

We now give some additional definitions pertaining to holes.

######  Definition 2.9.

Given a grid graph $\Gamma=(V_{\Gamma},E_{\Gamma})$ with inner holes
$\mathcal{H}$. Then the boundary of some $H\in\mathcal{H}$ is the set of nodes
whose corresponding points in the plane are on the geometric boundary
$\partial H$ of $H$. We say that a node is incident to $H$ if it is part of
its boundary. Similarly a node set (like a portal) is incident to $H$ if it
contains an incident node.

######  Definition 2.10.

A grid graph $\Gamma=(V_{\Gamma},E_{\Gamma})$ with $\mathcal{H}=\emptyset$ is
called simple.

Finally, [9] gives an efficient algorithm for the special case of computing
routing schemes in simple grid graphs. This implies a constant stretch routing
scheme for UDGs without holes by Theorem 2.4.

######  Theorem 2.11 (cf. [9]).

An exact routing scheme for a simple grid graph $\Gamma$ using node labels and
local space of $\smash{O}(\log n)$ bits can be computed in $\smash{O}(\log n)$
rounds in the $\mathsf{HYBRID}$ model.

##  3 Closest Point Computations in Simple Grid Graphs

In this section, we aim to present two important subroutines for our main
results. First, we present an $\mathcal{O}(\log n)$ Single Source Shortest
Paths problem (SSSP) algorithm for simple grid graphs. The problem input is
given by the grid graph in a distributed way (each node initially knows only
its incident edges) and it is solved as soon all nodes know their distance to
a dedicated source node. Afterwards, we use this algorithm to solve a problem
we call the _Single Portal Shortest Path_ problem (SPSP). Here, we want to
compute the distance of each node to its corresponding closest point some
dedicated portal (Def. 2.7). We start with the following theorem.

######  Theorem 3.1.

Given a simple grid graph $\Gamma$, we can solve SSSP on $\Gamma$ in
$\mathcal{O}(\log n)$ rounds.

To achieve this runtime bound, we split the SSSP problem into its vertical and
horizontal parts, i.e., we compute SSSP solutions with respect to vertical and
horizontal distances separately and show that these can be combined to obtain
the actual distance (which requires that $\Gamma$ is simple). We start by
defining two auxiliary graphs are used to compute distances in these two
directions.

Figure 1: A simple grid graph (left) and the corresponding horizontal (center)
and vertical (right) portal graphs.

######  Definition 3.2.

Given a grid graph $\Gamma$, we define the _vertical portal graph_
$\mathcal{P}_{v}$ to be the the graph with vertices corresponding to the
vertical portals of $\Gamma$. Two vertices in $\mathcal{P}_{v}$ are connected
by an edge iff their corresponding portals are adjacent (i.e., connected with
a horizontal edge) in $\Gamma$. The horizontal portal graph $\mathcal{P}_{h}$
is defined analogously.

As we will see later, the distances in $\mathcal{P}_{v}$ correspond to
horizontal distances taken by paths and those in $\mathcal{P}_{h}$ correspond
to vertical distances, respectively. This motivates us to run SSSP on these
graphs and combine the solutions.

######  Lemma 3.3.

If a grid graph $\Gamma$ is simple, both its vertical portal graph
$\mathcal{P}_{v}$ and its horizontal portal graph $\mathcal{P}_{h}$ are trees.

######  Proof 3.4.

For simplicity, we state the proof for the vertical portal graph
$\mathcal{P}_{v}$, the claim for $\mathcal{P}_{h}$ follows by symmetry. We
prove the claim by contradiction. Assume there was a cycle in
$\mathcal{P}_{v}$. This cycle would correspond to a set of portals in
$\Gamma$, such that two adjacent nodes in the cycle correspond to two adjacent
portals in $\Gamma$. We pick two portals from this set that have the same $x$
coordinate arbitrarily. Such a pair must exist due to the existence of a cycle
in $\mathcal{P}_{v}$. As the portals are maximal vertically connected
components by definition, there is some space enclosed between them. Further,
as the portals are part of a cycle in $\mathcal{P}_{v}$, they are connected by
two paths in $P_{v}$. Starting from the northern portal of the pair we picked,
one of those paths surround the area between the pair of portals in a
clockwise direction, while the other surrounds it in a counter-clockwise
direction. Together, they enclose it and it must correspond to the hole, which
contradicts simplicity.

color=yellow!50]Julian: I reworked the proof. It is a little handwavey now. I
think it is fine, though. Do you agree?

This allows us to employ a slightly modified version of the hybrid SSSP
algorithm for trees presented in [12, Theorem 6].

######  Lemma 3.5.

Given a simple grid graph $G$, we can solve SSSP on its vertical and
horizontal portal graph in time $\mathcal{O}(\log n)$.

######  Proof 3.6.

The algorithm of [12] can be used to compute a SSSP solution in trees in time
$\mathcal{O}(\log n)$ in the $\mathsf{HYBRID}$ model. Therefore, it suffices
to construct a subgraph of $\Gamma$ that maintains the tree structure and the
distances of $\mathcal{P}_{v}$. It consists of all nodes of $\Gamma$ and all
vertical edges. For each pair of adjacent portals in $\mathcal{P}_{v}$ we add
a _single_ arbitrary horizontal edge connecting the two portals. Note that
identifying adjacent pairs of portals and one edge that connects those can be
done in $\smash{O}(\log n)$ rounds in the $\mathsf{HYBRID}$ model. We achieve
this, by first employing _pointer jumping_ on the portal to aggregate and
broadcast (Lemma C.3) the minimum identifier, acting as a portal identifier.
Each node informs its horizontal neighbors about its own portal’s identifier.
Next the nodes communicate with their vertical neighbors, which identifiers
they have received this way. This allows the bottommost node neighboring a
specific portal to mark its edge in the corresponding direction as the edge
connecting the two portals. As vertical portals are maximal vertically
connected subgraphs, this selection is unique. To preserve the distances in
$\mathcal{P}_{v}$ we simply assign a weight of $1$ to all horizontal $0$ to
all vertical egdes. The procedure for $\mathcal{P}_{h}$ works analogous
(exchange the words horizontal and vertical).

Next, we combine the SSSP solutions for $\mathcal{P}_{v}$ and
$\mathcal{P}_{h}$ into a SSSP solution for $\Gamma$.

######  Lemma 3.7.

Given a simple grid graph $\Gamma$, a starting node $s$ and SSSP solutions for
its vertical and horizontal portal graphs $\mathcal{P}_{v}$ and
$\mathcal{P}_{h}$ starting from the corresponding portals containing $s$, we
can compute an SSSP solution for $\Gamma$ starting from $s$ in time
$\mathcal{O}(\log n)$.

######  Proof 3.8.

Each node computes its distance to $s$ in $\Gamma$ by adding the two distances
obtained by the SSSP computations in $\mathcal{P}_{v}$ and $\mathcal{P}_{h}$.
To show the correctness of these distances, we perform an inductive argument
along the shortest paths. Let $w\in V$ be an arbitrary node and denote its
computed vertical distance with $d_{v}(w)$ in and its computed horizontal
distance with $d_{h}(w)$. Consider a shortest path
$(s=w_{1},\dots,w_{\ell}=w)$ from $s$ to $w$. Since both portals containing
$s$ correspond to the starting nodes of the SSSP executions in
$\mathcal{P}_{v}$ and $\mathcal{P}_{h}$, both distances $s$ obtained by the
procedure described above are $0$, i.e., we have $d(s)=d_{v}(s)+d_{h}(s)=0$,
which is our base case. Next, we argue that
$d(w_{n})=d_{v}(w_{n})+d_{h}(w_{n})$ implies
$d(w_{n+1})=d_{v}(w_{n+1})+d_{h}(w_{n+1})$, for $n+1\leq\ell$. Note that node
$w_{n+1}$ is node $w_{n}$’s successor in the shortest path and further away
from $s$ than it by construction. If it is vertically adjacent to $w_{n}$, we
have $d_{v}(w_{n+1})=d_{v}(w_{n})+1$ and $d_{h}(w_{n+1})=d_{h}(w_{n})$.
Naturally, $d(w_{n+1})=d(w_{n})+1$ also holds. Therefore, we have
$d(w_{n+1})=d(w_{n})+1=\left(d_{v}(w_{n})+1\right)+d_{h}(w_{n})=d_{v}(w_{n+1})+d_{h}(w_{n+1})$.
The case where the shortest path makes a horizontal step is analogous.
color=yellow!50]Julian: reworked the proof and removed one of the cases for
easier reading

Since the distance values are correct and the predecessor pointers are picked
to point to any neighbor closer to $s$, their correctness immediately follows.

Using Lemma 3.5, we combine the SSSP solutions for the portal graphs
$\mathcal{P}_{v}$ and $\mathcal{P}_{h}$ to compute an SSSP solution for the
grid graph $\Gamma$, which allows us to conclude Theorem 3.1. We can extend
Theorem 3.1 to compute the distance of each node in a grid graph to a
dedicated portal $P$. We refer to this problem as the _Single Portal Shortest
Path_ (SPSP) problem. To solve the SPSP problem, we pick an arbitrary node of
$P$ as the starting node of an SSSP execution and consider the weights of all
edges of $P$ to be zero during that execution.

######  Corollary 3.9.

Given a simple grid graph $\Gamma$ and a portal $P$ in $\Gamma$. We can
compute the distances of every vertex in $\Gamma$ to $P$ and its neighbor that
is closest to $P$ in time $\mathcal{O}(\log n)$.

We conclude this section with an observation on how to compute a shortest path
tree using the distance values of an SSSP computation or an SPSP computation.

[Shortest Path Tree] After computing SSSP (or SPSP), by having each node pick
a predecessor pointer arbitrarily from its neighbors with minimal distance to
$s$ we can establish the corresponding shortest path tree in a distributed
sense (this step takes just $\mathcal{O}(1)$ time using local edges).

##  4 Pathconvex Region Decomposition

In this section we establish that grid graphs can be partitioned into
comparatively few sets of nodes (with some overlap at the borders) called
regions that are simple, i.e., they have no holes and path-convex, which we
define as follows.

######  Definition 4.1 (Path Convexity).

Let $\Gamma=(V,E)$ be a grid graph and let $R\subseteq V$. Then $R$ is called
_path-convex_ if for any pair $u,v\in R$ there is a shortest $uv$-path
contained completely within that region.666This leans on the standard
definition of convex node sets in the context of graphs. A node set is called
convex if all (instead of just one) shortest paths between any pairs of nodes
are within the set. We say that a region is path-convex with respect to a set
of points in that region, if there is a shortest path between any pair of
those points that stays within the region.

######  Definition 4.2 (Region Decomposition).

Let $\Gamma=(V,E)$ be a grid graph. A region decomposition of $\Gamma$ is a
family of connected node sets $\mathcal{R}=\\{R_{1},\dots,R_{\ell}\\}$
(regions) with $V=R_{1}\cup\dots\cup R_{\ell}$. We call a region _simple_ if
it has no inner holes (c.f., Definition 2.8). We call $\mathcal{R}$ simple and
path-convex if all regions in $\mathcal{R}$ are simple and path-convex (c.f.,
Definition 4.1).

For the implementation, we will achieve a simple and convex region
decomposition $\mathcal{R}$ by disconnecting parts of $\Gamma$ and considering
each connected component as a separate region. For this we create copies of
nodes that are on the border of at least two regions and connect each copy
only to neighbors in one of those region.

The construction breaks down into three main steps. In the first step, we
decompose $\Gamma$ into simple regions. Second, we break those regions up
further into “tunnels”, which are defined by the property that they overlap in
at most two portals (called gates) with all of their neighboring regions. In
the final step we show that such tunnels have crucial properties that allows
us to make them convex by subdividing them a constant number of times.
Ultimately, we prove the following theorem.

######  Theorem 4.3.

For any grid graph $\Gamma$, a decomposition into $\smash{O}(|\mathcal{H}|)$
simple, path-convex regions can be computed in $\smash{O}(|\mathcal{H}|+\log
n)$ rounds in the $\mathsf{HYBRID}$ model.

Splitting Operations. To achieve the desired region decomposition we split the
the grid graph at strategic locations. The most basic such operation is to
split a grid graph (or a region) at some portal, where each node will simulate
two copies of itself, a “right copy” which has no left neighbor and a “left
copy” which has no right neighbor. This establishes a new grid graph where
nodes that have been split will act in the role of the nodes they simulate
only, which blocks paths through the splitting portal and might disconnect
$\Gamma$.

If such a splitting portal touches the boundary of a hole, we often further
split at a boundary node. in particular, we split the simulated boundary node
that is on the “same side” as the hole (say the left copy if the hole is left
of the portal) into a “top” and “bottom” copy, which do not have a bottom or
top neighbor, respectively. This is where up to three regions may intersect in
the resulting region decomposition and can also be used to break up cycles
around a hole, thereby making the resulting regions simple. We describe such
splitting operations in detail and prove that they can be conducted
efficiently in Appendix C.3, Definition C.11 and Lemma C.12.

We often talk of the region decomposition in the sense of Definition 4.2 after
conducting such a split. It is given implicitly by the connected components in
the grid graph formed by the simulated nodes after splitting at a portal or a
node according to Definition C.11. As a consequence of these splits, during
intermediate steps, we occasionally end up with (unconnected) copies of some
grid node within the same region thus we have to slightly generalize our
notion of grid graphs to accommodate for those.

Since we split at portals, we obtain the property that regions overlap only in
node sets that form portals (i.e., maximal vertically connected components).
To distinguish those from ordinary portals (Def. 2.7), we call these _gates_ ,
which we formally define as follows.

######  Definition 4.4 (Gate).

Let $\Gamma$ be a (simulated) grid graph after splitting at some vertical
portal (according to Appendix C.3 Definition C.11) has been conducted (the
case with a horizontal portal is symmetric). Then a node on that portal is
called a _gate node_. A maximal vertically or horizontally connected component
of gate nodes within a given region of the resulting decomposition after the
split is called a _gate_.

Note that in the subsequent sections, gates will be vertical until the last
step. Furthermore, we classify connected segments of the boundary nodes of
some region, which are not on gates. We will refer to these as _walls_ ,
formally defined as follows.

######  Definition 4.5 (Wall).

Let $\mathcal{R}$ be a region decomposition of $\Gamma$ established by
conducting splitting operations as defined in Appendix C.3 Definition C.11.
For $R\in\mathcal{R}$ We denote _connected_ segments of hole boundary nodes in
$R$ (see Def. 2.9) that are _not_ gate nodes (cf. Def. 4.4) as _walls_. Note
that walls and gates alternate on the boundary of $R$. Also note that
different wall segments might share nodes.

###  4.1 Decomposition into Simple Regions

The first step is to split our grid graph into _simple_ regions, i.e., regions
without holes. We show that a relatively simple region decomposition can
achieve this goal and give the implementation details of the construction
separately.

######  Definition 4.6 (Splitting $\Gamma$ into Simple Regions).

For each inner hole $H\in\mathcal{H}$ of $\Gamma$ we repeat the following. Let
$v_{H}$ be the leftmost node on the boundary of $H$ (we make $v_{H}$ unique by
choosing the northernmost among leftmost boundary-nodes). Let $P_{H}$ be the
unique vertical portal with $v_{H}\in P_{H}$. We conduct splits at $P_{H}$ and
$v_{H}$ (for the details, see Definition C.11 case two and three). In general,
$P_{H}$ might contain leftmost nodes of boundaries of different inner holes.
In that case we conduct the vertical split at the northernmost node of each
such hole, as described in the third case of Definition C.11 (and each such
inner hole needs not be considered further in the iteration over
$\mathcal{H}$). Figure 2 shows an example of the procedure.

Figure 2: Decomposition of grid graph into simple regions by splitting at
certain portals & nodes.

(a) A stylised grid graph with holes, where white areas are occupied by grid
nodes and shaded areas correspond to holes (see Def. 2.8).

(b) Red lines mark portals through a leftmost node of some hole at which a
split occurs. Further splits take place at a dedicated leftmost node of each
hole (details in Def. C.11).

The connected components that result from the above construction form regions
that are simple. The idea is that each such split will make the grid graph at
the portal $P_{H}$ horizontally impassable and at $v_{H}$ vertically
impassable. Roughly speaking, the split at a portal and a node on the portal
and hole boundary creates a “thin” hole such that in the resulting graph two
holes “merge”, and become a single hole. This decreases the overall number of
inner holes by one. By repeating this split for each inner hole we will be
left with one hole in the end, which is the outer hole.

However, splitting portals this way leads to “infinitely thin hole sections”
which does not fit with our definition of holes (Definition 2.8). Therefore,
we use as an auxilliary construction a grid graph with finer granularity
$1/3$. This construction has the same topological properties, and the
Definition 2.8 can be applied again. It can be modified such that it becomes
simple, and finally it can be transformed back into a grid graph with normal
granularity such the result equals exactly the one from the construction
above. In the following, we give the detailed work on this, in particular we
show the following two lemmas:

######  Lemma 4.7 (Correctness of Simple Decomposition).

The construction in Definition 4.6 decomposes $\Gamma$ into at most
$|\mathcal{H}|\\!+\\!1$ simple regions.

######  Lemma 4.8 (Computing the Simple Decomposition).

A _simple_ region decomposition can be computed for any grid graph $\Gamma$ in
$\smash{O}(\log n)$ rounds in the $\mathsf{HYBRID}$ model.

For the proof, we start with the Definition of the grid graph of granularity
1/3.

######  Definition 4.9 ($1/3$-Grid Transformation).

We transform a grid graph $\Gamma=(V_{\Gamma},E_{\Gamma})$ into a grid graph
$\Gamma^{\prime}=(V_{\Gamma^{\prime}},E_{\Gamma^{\prime}})$ that has
granularity $\frac{1}{3}$ as follows. For each node $v\in V_{\Gamma}$ at
position $(a,b)\in\mathbb{Z}^{2}$, we create nine nodes in
$V_{\Gamma}^{\prime}$ at positions $(a\\!+\\!x,b\\!+\\!y)$ with
$x,y\in\\{-\frac{1}{3},0,\frac{1}{3}\\}$. We say that
$u^{\prime},v^{\prime}\in V_{\Gamma^{\prime}}$ belong to the group of $v\in
V_{\Gamma}$ if they were created from $v$ (i.e., rounding their coordinates to
the closest integer gives the position of $v$). For each pair
$u^{\prime},v^{\prime}\in V_{\Gamma}$ We add an edge
$\\{u^{\prime},v^{\prime}\\}$ to $E_{\Gamma^{\prime}}$ between two nodes
$u^{\prime},v^{\prime}\in V_{\Gamma^{\prime}}$ if
$\|u^{\prime}\\!-\\!v^{\prime}\|_{2}=\frac{1}{3}$. An edge
$\\{u^{\prime},v^{\prime}\\}\in E_{\Gamma^{\prime}}$ is assigned weight 0 if
$u^{\prime},v^{\prime}$ belong to the same group, else weight 1.

We will decompose the transformed graph
$\Gamma^{\prime}=(V_{\Gamma^{\prime}},E_{\Gamma^{\prime}})$ with a procedure
similar to the one proposed for $\Gamma$ and make an argument that it is
simple, i.e., no region has any holes. Afterwards we “round” the nodes of
$\Gamma^{\prime}$ back to the integer grid and argue that a) the region
decomposition is still simple and b) That the final result is exactly the same
as doing the procedure in Definition 4.6 for $\Gamma$. The reverse
Transformation works as follows.

######  Definition 4.10 (Reverse Transformation).

We transform a grid graph
$\Gamma^{\prime}=(V_{\Gamma^{\prime}},E_{\Gamma^{\prime}})$ that has
granularity $\frac{1}{3}$ back into a grid graph
$\Gamma=(V_{\Gamma},E_{\Gamma})$ with granularity 1. Note that the resulting
graph may have nodes sharing the same coordinate. For $p\in\mathbb{Z}^{2}$ Let
$V_{p}$ be the set of nodes in $V_{\Gamma^{\prime}}$ whose coordinates are $p$
when rounded to the closest integer. Let $\tilde{u},\tilde{v}$ be two
connected components in $V_{p}$. We create a new node $V_{\Gamma}$ at $p$, for
each connected component (this is where the nodes occupying the same
coordinate can occur). Finally we define the edges of $\Gamma$. Let
$p_{1},p_{2}\in\mathbb{Z}^{2}$ and let $\tilde{u}$, $\tilde{v}$ be connected
components in $V_{p_{1}}$ and $V_{p_{2}}$, respectively, i.e.,
$\tilde{u},\tilde{v}\in V_{\Gamma}$. We add an edge
$\\{\tilde{u},\tilde{v}\\}$ between nodes $\tilde{u},\tilde{v}\in V_{\Gamma}$,
if there are two nodes $u\in\tilde{u}$ and $v\in\tilde{v}$ with $\\{u,v\\}\in
E_{\Gamma^{\prime}}$, i.e., $u,v$ share an edge in $\Gamma^{\prime}$.

The next definition gives an iterative construction on how to make
$\Gamma^{\prime}$ simple.

######  Definition 4.11 (Construction to remove $H$ in $\Gamma^{\prime}$).

Let $\Gamma^{\prime}$ be the $1/3$ Transformation of a grid graph $\Gamma$.
For each inner hole $H\in\mathcal{H}$ of $\Gamma$ we repeat the following. Let
$v_{H}$ be the splitting node, i.e., the chosen leftmost node on the boundary
of $H$. Let $v^{\prime}_{H}\in V_{\Gamma^{\prime}}$ be the middle node (the
one with coordinates in $\mathbb{Z}$) of the 9 nodes created from $v_{H}$ in
$\Gamma^{\prime}$. Let $P^{\prime}_{H}$ be the unique portal in
$\Gamma^{\prime}$ with $v^{\prime}_{H}\in P^{\prime}_{H}$. We remove all nodes
on $P^{\prime}_{H}$ from $\Gamma^{\prime}$ as well as the node right of
$v^{\prime}_{H}$ (which is at the boundary of some hole in $\Gamma^{\prime}$).
If there is a splitting node $v_{H^{\prime}}$ of another hole $H^{\prime}$
with $P_{y}$ we repeat the same procedure for $v_{H^{\prime}}$ in
$\Gamma^{\prime}$.

######  Proof 4.12 (Proof of Lemma 4.7).

When splitting at some hole $H\in\mathcal{H}$ (according to the procedure in
Definition C.11) we introduce at most one additional connected component, i.e.
one additional region, in case $P_{H}$ is a node separator777A node separator
w.r.t. two nodes $u,v$ is a set of nodes, the removal of which decomposes the
graph into (at least) two connected components, where $u,v$ are in different
components. in its current region. Note that, even though we also split at
$v_{H}$, the region to the right of $P_{H}$ will remain connected via the
boundary of $H$ (we end up with two copied nodes at the position of $v_{H}$ in
the same region, though). Hence the number of regions is at most
$|\mathcal{H}|\\!+\\!1$.

The idea to prove the simple property is that each split of the grid graph as
described in the procedure above (Def. 4.6), will make the portal $P_{H}$
impassable in horizontal direction and $v_{H}$ impassible in vertical
direction. Loosely speaking, in the resulting grid graph at least two holes
will “merge”, and become one hole. After repeating this for all holes, we
obtain a grid graph with a single hole, namely the outer hole, i.e., it is
simple (Def. 2.10).

However, the idea to “merge” holes via an impassable portal is not
reconcilable with our definition of holes 2.8. Thus we use a
$1/3$-transformation to $\Gamma^{\prime}$, where we can show that at least two
holes merge using our formal definition with an analogous construction in
$\Gamma^{\prime}$ (Def. 4.11). We then argue that the reverse transformation
of the resulting simple graph with granularity $1/3$ corresponds to the same
grid graph that we obtain with the original procedure has the same topology,
that is, the same number of holes per region, i.e., none.

Let $H$ be said hole with splitting node $v_{H}$. Let $\Gamma^{\prime}$ be the
the $1/3$-transformation of $\Gamma$ after removing $H$ as per the
construction explained above. After the construction, the transformed nodes
from the Portal $P_{y}$ form a “channel”, which connects $H$ with at least one
other hole, as otherwise $v_{H}$ could not have been the leftmost node. Hence
the number holes in $\Gamma^{\prime}$ decreases by at least one.

After repeating the above for all nodes, the remaining nodes in
$\Gamma^{\prime}$ only have a single hole left, the outer hole. This is
equivalent to the fact that for any pair of nodes, two paths in
$\Gamma^{\prime}$ between those nodes (if any exist) can be continuously
transformed into one another within $S_{\Gamma^{\prime}}$ (see Def. 2.8),
i.e., without “transforming” paths through holes. The same follows for any
pair of nodes in $\Gamma$, as $\Gamma$ does not admit the passing of the same
portals which we “channeled” in $\Gamma^{\prime}$. This is equivalent to the
fact that $\Gamma$ has only one hole, the outer hole.

######  Lemma 4.13.

After the construction to remove holes in $\Gamma$ (Def. 4.6), the only nodes
that share coordinates are two copies of splitting nodes $v_{H}$.

######  Proof 4.14.

For a contradiction assume that after executing the construction (Def. 4.6) in
$\Gamma$, the left and right node copies, say $v_{\ell}$ and $v_{r}$ of
$P_{H}$ are in the same connected component (region). Then there is a
$v_{\ell},v_{r}$-path within that region. Since $P_{H}$ can not be crossed,
that path must enclose at least one other inner hole (which touches on of the
end nodes of $P_{H}$). But then this path would also have to cross the
splitting portal $P_{H^{\prime}}$ of at least one inner hole $H^{\prime}$,
which is a contradiction.

We show that the procedure in Definition 4.6 can be conducted in
$\smash{O}(\log n)$ rounds.

######  Proof 4.15 (Proof of Lemma 4.8).

In Appendix C.2 and Appendix C.3 we describe a few basic primitives that
allows us to conduct broadcasts and aggregations on paths and cycles in
$\smash{O}(\log n)$ rounds. Note that these procedures can be done in parallel
in case such structures intersect only $\smash{O}(1)$ times in each node. Also
note that portals and boundaries of holes form paths and cycles with only
$\smash{O}(1)$ intersections per node.

Using these primitives, it is easy to establish splitting nodes $v_{H}$ and
splitting Portals $P_{H}$ (see Definition 4.6) by broadcasting the minimum
$x$-coordinate on the boundary of $H$ (breaking ties by maximum $y$
coordinate) and subsequently informing the nodes on $P_{H}$ of their role as
nodes on a splitting portal. We do this in parallel for each $H$ and $P_{H}$
(note that only one broadcast has be conducted on $P_{H}$ in case $P_{H}$ is
splitting portal for multiple holes). Determining the roles of nodes is the
main part, the subsequent splitting procedure and simulation overhead takes
just $\smash{O}(1)$ rounds by Lemma C.12.

###  4.2 Decomposition into Tunnel Regions

Our next step is to ensure that each region is a _tunnel_ , which we define as
a region that has at most two gates (see Def. 4.4). Recall that as a
consequence of the previous Section 4.1, we start out with a grid graph
$\Gamma$ that is decomposed into simple regions (cf. Lemma 4.7).

######  Remark 4.16.

Recall that the boundary of each region is composed of alternating segments of
walls and vertical gates (cf. Def’s 4.4, 4.5). Being a member of a wall or a
gate of some region is a condition that each node can determine locally.
Furthermore, walls and gates can both compute unique identifiers in $O(\log
n)$ rounds, using our procedures for aggregation and broadcast in Appendix C.1
(Lemma C.3).

In the following, we say that two vertical portals (cf. Def. 2.7) are adjacent
to each other, if at least two nodes of either portal are endpoints of a
horizontal grid edge. The notion of walls and gates allows us to define
_junction portals_ that we require for the next stage of our decomposition.
Informally, a junction portal is a portal at which a simple region “diverges”
into at least three “tunnels” (although there are some degenerate cases for
such junction portals, where a gate cuts away one of these “tunnels”).
Formally we define (see also Figures 3(a) and 3(c)):

######  Definition 4.17 (Junction Portals).

Let $R$ be a simple region. A vertical portal $P$ in $R$ is a _junction_
portal if:

  1. i.

$P$ has at least $3$ adjacent portals each intersecting at least 2 distinct
walls; or

  2. ii.

$P$ is a gate, and has at least $2$ adjacent portals each intersecting at
least 2 distinct walls.

The idea is to perform portal splitting operations (as described in Appendix
C.3 Definition C.11) on each junction portal and on specific nodes on the
junction portal in order to separate these divergent tunnels. More
specifically the construction works as follows.

######  Definition 4.18 (Splitting at Junction Portals).

Let $P$ be a junction portal. We note that Definition 4.17 implies that there
are at least $2$ adjacent portals which each intersect multiple distinct walls
to the left of $P$ or to the right of $P$, or both. Suppose that portals
$P_{1},P_{2},\dots,P_{k}$ are such portals with the property of intersecting
distinct walls _to the left_ of $P$ and let these portals be ordered from
north to south (the procedure for those to the right is analogous).
We first conduct a splitting operation at $P$ (Def. C.11 case 1).

Then, for each portal $P_{i},1\leq i<k\\!-\\!1$ we choose the bottommost node
on $P$ which is adjacent to some node on $P_{i}$ and split at this node (see
Def. C.11 case 2+3). Note that this node must coincide with a hole boundary,
since one of the two portals does not extend further south. Finally, note that
this procedure effectively splits off each region that is bordered by one of
the portals $P_{i}$ since $R$ is simple.

The goal of this section is the following three lemmas pertaining to the
number of regions created, and the correctness and computational complexity of
the construction:

######  Lemma 4.19 (Computation of Tunnel Decomposition).

Given a decomposition into simple regions, finding and splitting all junction
portals can be done in $O(\log n)$ rounds.

######  Lemma 4.20 (Correctness of Tunnel Decomposition).

All of the regions resulting from the procedure of finding splitting portals
and splitting them are bounded by at most two walls and two gates.

######  Lemma 4.21 (Regions after Splitting Junctions).

After decomposing all junctions into tunnels with the procedure above
(Definition 4.18), the resulting number of regions is $O(|\mathcal{H}|)$.

We first give a proof of Lemma 4.19, which states that junction portals can be
found and split in parallel in $O(\log n)$ rounds of the $\mathsf{HYBRID}$
model:

######  Proof 4.22 (Proof of Lemma 4.19).

Nodes can determine whether their portal is incident to multiple distinct
walls in $O(\log n)$ rounds as follows. Nodes broadcast any incident wall IDs
to all other nodes on their portal. As soon as a node receives two wall IDs it
instead broadcasts message “yes”, indicating that the portal is incident to
multiple distinct walls. If a node receives the message “yes”, it stops what
it was doing and starts broadcasting the message “yes” for $O(\log n)$ rounds.
If no node receives two wall IDs or the message “yes” in $O(\log n)$ rounds
then nodes can conclude that their portal is _not_ incident to multiple walls.
Each node can then inform their neighbors in one round whether its portal is
incident to multiple distinct walls.

In the same way, each portal can determine whether it satisfies the criteria
to be a junction portal (all nodes on a portal know whether or not the portal
is a gate, and therefore know which case of Definition 4.17 is required).
Finally, each node $v$ can locally determine whether it is split if its portal
is a junction portal. If the node to the right of $v$ (resp. to the left of
$v$) is on a portal incident to multiple distinct walls, and the node below
and to the right to $v$ is not, then $v$ is to be split. Finally, the
splitting can be performed according to Def. C.11 in $O(\log n)$ rounds, per
Lemma C.12.

Next, we introduce a tree structure which will be useful for the proofs of
Lemmas 4.21 and 4.20. This structure is used for the purpose of proving claims
only, we need not actually construct it.

######  Definition 4.23 (Portal Tree Without Cavities).

Given a simple region $R$, consider the vertical portal graph $\mathcal{P}$ of
the region $R$ as in Definition 3.2. As $R$ is simple, by Lemma 3.3
$\mathcal{P}$ is a tree. Remove all leaves of $\mathcal{P}$ which correspond
to portals which only intersect one wall. Repeat this until no such leaves
remain in $\mathcal{P}$. We call this the _portal tree without cavities_ of
$R$.

A visual example of a portal tree without cavities is given in Figure 3(b).

Figure 3: An explanation of junction portals and the portal tree without
cavities.

(a) An example of case (i) of Definition 4.17. Blue portals are pre-existing
gates. The red portal is a junction portal, because it has three adjacent
portals (shown in green) which are incident to multiple distinct walls.

(b) An example of a vertical portal tree (corresponding to the example in
Figure 3(a)). The orange nodes and edges would be removed, giving us a portal
tree without cavities. In the remaining graph, blue nodes correspond to gates,
and the red node corresponds to a junction portal.

(c) An example of case (ii) of Definition 4.17. The blue portals are pre-
existing gates. The red portal is also a pre-existing gate, and it is adjacent
to three portals which intersect multiple distinct walls (in green), so it is
a junction portal.

######  Lemma 4.24.

Consider a simple region $R$ and an associated portal tree without cavities
$\mathcal{P}$ (as in Definition 4.23). The following statements all hold:

  1. 1.

Since we have only removed leaves from the portal tree, $\mathcal{P}$ remains
connected (or empty).

  2. 2.

All portals corresponding to nodes in $\mathcal{P}$ are incident to multiple
distinct walls.

  3. 3.

All remaining leaves in $\mathcal{P}$ correspond to gates.

  4. 4.

The portal tree $\mathcal{P}$ contains all junction portals in $R$.

  5. 5.

Iff a node in $\mathcal{P}$ has degree at least $3$, or corresponds to a gate
and has degree at least $2$, then it corresponds to a junction portal.

######  Proof 4.25.

We take the statements in order:

  1. 1.

Removing leaves does not disconnect a tree.

  2. 2.

We will prove this by contradiction. Fix a portal $P$ which corresponds to a
node in $\mathcal{P}$, and suppose it is only incident to one wall, $W$. Let
$p_{\uparrow}$ and $p_{\downarrow}$ be the top and bottom points of $P$; both
are incident to $W$. Since region boundaries are alternating sequences of
walls and gates, we must have that $p_{\uparrow}$ and $p_{\downarrow}$ are
connected by some sub-path of $W$. Call this sub-path $W^{\prime}$ and suppose
wlog that $W^{\prime}$ meets $p_{\uparrow}$ and $p_{\downarrow}$ from the
left. Consider $R^{\prime}$: the subregion of $R$ bounded by $P$ and
$W^{\prime}$. Clearly $R^{\prime}$ must be simple, and therefore no other hole
can appear in $R^{\prime}$.

Note that $P$ cannot have degree $1$ in $\mathcal{P}$, otherwise we would have
removed it from $\mathcal{P}$. So $P$ must have at least two adjacent portals
which are incident to multiple walls: let $P_{1}$ and $P_{2}$ be two such
portals. Furthermore $P_{1},P_{2}$ must be to the right of $P$ since the
cavity $R^{\prime}$ is to its left. If either $P_{1}$ or $P_{2}$ of $P$ would
start and end with nodes in $W$ this would be the beginning of another cavity
$R^{\prime\prime}$, and by the same argument in the previous paragraph would
have already been removed from $\mathcal{P}$. Therefore, $P_{1}$ and $P_{2}$
must have at least one wall other than $W$ as one of their endpoints.

In order that $P$ can be incident to _two_ portals to its right, it must have
an the interior of a hole immediately to the right of $P$ that “separates”
these. By our assumption, since the boundary of this hole intersects $P$ it
must belong to the wall $W$. And so $P_{1}$ and $P_{2}$ must both have one
endpoint in $W$ to the right of $P$ as well. Combined with the above statement
this implies that $P_{1},P_{2}$ each have exactly one endpoint in $W$ (which
is to the right of $P$) and another endpoint in another wall. Since $W$ must
be contiguous, the section of $W$ to the right of $P$ must connect to either
$p_{\uparrow}$ or $p_{\downarrow}$ and thus intersect both endpoints of at
least one of the two portals $P_{1},P_{2}$. This is a contradiction to the
fact that both $P_{1}$ and $P_{2}$ must have an endpoint in a wall which is
not $W$.

  3. 3.

All remaining leaves must be incident to multiple distinct walls, by the
previous statement. For a contradiction, fix a leaf which corresponds to a
portal $P$ but is not a gate. Note that $P$ is only incident to one portal
which remains in $\mathcal{P}$, suppose wlog that it is to the right of $P$.

If there is no portal to the left of $P$ in $R$, then $P$ is a section of
$W_{1}$ (by our assumption that $P$ is not a gate). Some node along $P$ must
be part of a different wall $W_{2}$, otherwise $P$ would have been removed.
Let $p_{\uparrow}$ be the node to the right of the topmost node on $P$ which
intersects $W_{2}$, and let $p_{\downarrow}$ be the node to the right of the
bottom-most node on $P$ which intersects $W_{2}$. $p_{\uparrow}$ and
$p_{\downarrow}$ are both on different vertical portals to the right of $P$,
and both of their portals intersect $W_{1}$ and $W_{2}$. This contradicts that
$P$ is a leaf in $\mathcal{P}$.

If there is a portal to the left of $P$, then it must be incident to only one
wall, $W$ (otherwise $P$ would not be a leaf). If both endpoints of $P$ are
incident to $W$, then the logic from the previous paragraph applies: some node
on $P$ must be incident to a different wall, implying that $P$ has two portals
to its right which intersect distinct portals. So suppose this is not the
case, and that one of the endpoints of $P$ (wlog the top-most endpoint) is
incident to a different wall $W^{\prime}$. Let $v$ be the topmost point on $P$
which intersects $W$. The point immediately to the left of $v$ must lie on a
vertical portal which intersects $W$ (since $v$ intersects $W$) and
$W^{\prime}$. This is a contradiction, since by assumption no portal to the
left of $P$ is incident to multiple distinct walls.

  4. 4.

We argue that nodes which we removed could only be adjacent to at most one
portal which is incident to multiple walls, and therefore fail to satisfy the
definition in Definition 4.17. This is the case because nodes only have degree
$1$ when we remove them: they may previously have been connected to nodes
which we later removed, but the nodes which we later removed must only have
been incident to one wall.

  5. 5.

This claim immediately follows from statement 2, since this mirrors the
definition of junction portals given in Definition 4.17.

We now prove that the splitting procedure is correct (Lemma 4.20).

######  Proof 4.26 (Proof of Lemma 4.20).

Consider, for the sake of contradiction, a region $R$ has more than three
gates after all junction portals have been split. Consider the portal tree
described in Definition 4.23.

If this tree has at least $3$ leaves, then it must (graph-theoretically) have
a node with degree at least $3$. But this node is a junction portal by Lemma
4.24. If this tree has only $2$ leaves, it must have an internal node (with
degree at least $2$) which corresponds to a gate, due to our assumption that
$R$ has three gates. But by Lemma 4.24, this must also have been a junction
portal. Therefore both cases lead to a contradiction and no such region $R$
can exist.

Next, we observe that splitting a junction portal can lead to a “dead-end”
region, bounded by one gate and one wall. Note that a junction portal which
creates a dead-end region must have both endpoints incident to the same wall.
An example of this case is given in Figure 4. Note that each junction portal
can only create one dead-end region, since if there were a dead-end region on
each side, then there would be no adjacent portals which connect two distinct
walls (since each region is simple). Note also that if there is a dead-end
region on one side, then, since the region is simple and therefore consists of
alternating series of walls and gates, there can be no portal on that side
which connects two distinct walls. Therefore the junction portal is not split
on that side, and at most one dead-end region can be created on that side.

When splitting at a junction portal, this can result in at most one “dead-end”
region being created: that is, a region which is bounded by one gate and one
wall.

This happens when the junction portal only has one portal to its left (say)
which only intersects one wall. This cannot happen on both sides because then
it would not be a junction portal.

######  Proof 4.27.

Let $P$ be a junction portal, $W$ be a wall, and let there be a dead-end
region $R$ to the left (w.l.o.g.) of $P$ which is bounded by $P$ and $W$.
Since both ends of $P$ are on a wall, they must be on $W$.

First, notice that $R$ must be the only region to the left of $P$, since, if
there was a region to the left of $P$ which intersected two distinct walls,
then it would not be a dead end, and we would not cut $P$ between this region
and $R$, so $R$ would be a part of that region (we would call it a “cavity”).

If there was a dead-end region also to the right of $P$, then since the
endpoints of $P$ are on $W$, this region must also be bounded solely by $P$
and $W$. But we reach a contradiction, since this means that there could not
be any walls aside from $W$ in the region to the right of $P$, since the
regions are simple and region is only bounded by $P$ and $W$, and therefore
$P$ could not be a junction portal.

Figure 4: An example of a dead-end region, in blue. The junction portal (in
red) splits to the right, because there are at least three neighboring portals
which connect distinct walls. But it does not split to the left, and so a
dead-end region is formed.

Next, we prove Lemma 4.21: that the number of regions resulting from splitting
junction portals is not too large.

######  Proof 4.28.

We argue that a $k$-junction introduces at most $\smash{O}(k)$ new regions and
splitting portals. The claim then follows since the sum of gates of all
junctions are in $\smash{O}(|\mathcal{H}|)$.

Consider a region $R$ which was a $k$-junction (i.e. was bounded by $k$ gates)
after the decomposition into simple regions, and consider its portal tree
without cavities $\mathcal{P}$ as in Definition 4.23.

By Lemma 4.24 (3.) leaves of $\mathcal{P}$ must be gates of $R$ thus
$\mathcal{P}$ has $\ell\leq k$ leaves. Note that the remaining $k-\ell$ gates
of $R$ correspond to internal nodes of $\mathcal{P}$ (recall that these
correspond to case (ii) of Def. 4.17). The $\ell$ leaves imply that there are,
in the worst case, $\ell-2$ of degree at least $3$ in $\mathcal{P}$. Each of
these is incident to one dead end by Section 4.2. Then, each of these junction
portals is incident to $4$ regions created by splitting at junction portals,
giving $4\ell-8$ regions. Suppose (again in the worst case), that the $k-\ell$
internal nodes which are gates only have degree $2$. These gates are incident
to $2$ regions each created by splitting at these junction portals, giving
$2k-2\ell$. Summing these, and recalling that $\ell\leq k$, gives that at most
$\smash{O}(k)$ regions are created from a $k$-junction, as required.

Finally, we conclude with a lemma which will be useful for next section:
during the tunnel decomposition we get rid of almost all node copies within a
tunnel, except for the two copies of a splitting node.

######  Lemma 4.29.

In the tunnel decomposition obtained above, there can be at most one pair of
nodes that are copies of each other in each region. If that is the case, this
pair of nodes forms the two point shaped gates in their tunnel region.

######  Proof 4.30.

As the region decomposition is simple, we can not have any pair of
horizontally copied nodes in the same region as these would need to be
connected by a path encircling the hole north- or south-adjacent to their
corresponding portal. Hence we only need to consider the vertically copied
nodes introduced by a horizontal node split. As all splits added in this
section divide regions that are already simple, none of the resulting
vertically copied nodes can be in the same region. Hence all of them must be
created during the splitting into simple regions described in 4.6. At that
point we can still have more than one pair of vertically copied nodes, if the
leftmost node of two different hole boundaries align. As those two holes
induce two different walls and there must be at least one more wall, which may
be both above and below those holes, we must have a junction portal splitting
the two pairs of vertically copied nodes.

###  4.3 Path-Convex Decomposition

Finally, we make the tunnel regions that we obtained in the previous section
path-convex (cf. Def. 4.1), by splitting them at appropriate portals. For any
two nodes in such a tunnel with a shortest path in $\Gamma$ that travels
outside the tunnel, the additional portals with which we separate the region
will also separate that pair of nodes. We will also see that it is sufficient
to further separate tunnels at a constant number of vertical or horizontal
portals.

The main question that we answer in this section is where the tunnels shall be
split in order to make them path-convex. While the construction of the splits
is not too complicated, the main challenge is the proof of correctness, i.e.,
all “offending” node pairs whose shortest path runs outside of the region must
be separated. We answer this question in stages.

First, we impose the assumption that we have a tunnel region $T$ with gates
that are single nodes $g$ and $g^{\prime}$, see Figure 5. We show that we can
split $T$ into path-convex regions using only a horizontal and a vertical
portal $P_{x}$ and $P_{y}$. Roughly, if $d_{x}=d_{x,T}(g,g^{\prime})$ is the
horizontal distance from $g$ to $g^{\prime}$ in $T$ then all nodes which are
at distance $\frac{d_{x}}{2}$ to $g$ and $g^{\prime}$ will be part of $P_{x}$
(details in Def. 4.35), which we show forms a vertical portal (cf., Lemma
4.36). The horizontal portal $P_{y}$ is defined symmetrically. We split $T$ at
$P_{x}$ and $P_{y}$ (cf., Fig. 18).

As first part of our proof we show that two nodes $u,v$ that end up in the
same region $R$ after splitting at $P_{x}$ and $P_{y}$ that both lie on
(possibly different) shortest paths from $g$ to $g^{\prime}$ have a shortest
path within $R$ (see Lemma 4.43). Loosely speaking, this covers the well
behaved case where $u,v$ are not located in “cavities” of $T$. We then move on
to this harder case and show the same claim for any pair of nodes $u,v\in R$
(see Lemma 4.45) by using fundamental property of grid graphs (see Lemma B.16)
that lets us fall back to the easier case.

In the last stage of the construction, we remove the assumption that gates are
point-shaped. We distinguish two cases, depending on whether there is a
horizontal portal connecting the two gates (see Definition 4.47 and Figure 6).
We then give a decomposition procedure for each case, whereas the first case
(a) is well behaved and the second case (b) has the property that for any pair
of nodes in a region in the “middle part” a hypothetical shortest path that
goes outside $T$ can always leave and enter $T$ through two nodes
$g,g^{\prime}$ in the gates $G,G^{\prime}$, which allows us to fall back to
the proof of correctness for this case and split the “middle part” at
$P_{x},P_{y}$.

We conclude with lemmas pertaining to the number of regions created, the
correctness, and the computational complexity.

######  Lemma 4.31 (Regions after Convex Decomposition).

The construction in Definition 4.47 produces at most 10 regions for every
tunnel which we split.

######  Lemma 4.32 (Correctness of Path-Convex Decomposition).

The construction in Definition 4.47 (illustrated in Figure 6) decomposes $T$
into path-convex regions.

######  Lemma 4.33 (Computation of Path-Convex Decomposition).

The construction of the portals in Def. 4.47 and 4.35 and the described
splitting of the tunnel region $T$ takes $\smash{O}(\log n)$ rounds.

The lemmas from the three sections of the region decomposition can then be
combined to obtain the proof for Theorem 4.3: that our construction is
efficient and results in a path-convex region decomposition that is linear in
the number of holes.

######  Proof 4.34 (Proof of Theorem 4.3.).

We obtain a simple region decomposition in the claimed number of rounds by
Lemma 4.7. These simple regions can be transformed into tunnel regions, i.e.
regions with at most two gates, due to Lemma 4.20. Finally, we have shown that
we can further break up tunnels into convex regions by Lemma 4.32. The
computation of this decomposition requires $O(\log n)$ rounds in the
$\mathsf{HYBRID}$ model, by Lemmas 4.8, 4.19 and 4.33. The number of regions
is $\smash{O}(|\mathcal{H}|)$ by Lemmas 4.7, 4.21 and 4.31.

It remains to prove Lemmas 4.32 and 4.33. We will subdivide the approach into
several stages, where we iteratively remove some of the simplifying
assumptions by reducing the more general case to the simplified one.

Figure 5: Splitting a tunnel with gates consisting of single nodes.

In the first stage we assume the special case that the two gates of a tunnel
are points. We use the following construction to make $T$ path-convex. We
start with the following definition. A visual depiction of the splitting
procedure described in Definition 4.35 is given in Figure 5.

######  Definition 4.35 (Splitting Portals for tunnels with point shaped
gates).

Let $T$ be a tunnel region with two gates $g,g^{\prime}\in T$ each consisting
of a single node. Let $d_{x}:=d_{x}(g,g^{\prime})$ and
$d_{y}:=d_{y}(g,g^{\prime})$, which are well defined since a tunnel $T$ is
also simple. Let $P_{x}=\\{v\in T\mid
d_{x}(g,v)=\lceil\tfrac{d_{x}}{2}\rceil,d_{x}(g^{\prime},v)=\lfloor\tfrac{d_{x}}{2}\rfloor\\}$
and analogously $P_{y}=\\{v\in T\mid
d_{y}(g,v)=\lceil\tfrac{d_{y}}{2}\rceil,d_{y}(g^{\prime},v)=\lfloor\tfrac{d_{y}}{2}\rfloor\\}$.

######  Lemma 4.36.

The set $P_{x}$, respective $P_{y}$ (see Def. 4.35 and Figure 5) forms a
vertical, respective a horizontal portal in the tunnel region $T$ (the
simplicity property of tunnels suffices here). Each portal is a node separator
w.r.t. $g$ and $g^{\prime}$.

######  Proof 4.37.

By Definition 2.7, we have to show that $P_{x},P_{y}$, are maximal connected
components in the graph induced by horizontal or vertical edges, respectively.
Due to symmetry, it suffices to consider $P_{x}$. Let $a\in P_{x}$ and let
$P_{a}$ be the maximally vertically connected component of $a$. Any vertically
adjacent point to $a$ must be also be in $P_{x}$ since the horizontal distance
to $g$ and $g^{\prime}$ does not change, thus $P_{a}\subseteq P_{x}$.

Assume there is a node $b\in P_{x}\setminus P_{a}$. Note that since the
horizontal distances of $a,b$ to $g$ and $g^{\prime}$ add up to exactly
$d_{x}(g,g^{\prime})$, $a$ and $b$ must lie on $gg^{\prime}$ paths
$\Pi_{a},\Pi_{b}$ that are shortest w.r.t. the horizontal distance. The path
$\Pi_{b}$ can not visit any point in $P_{a}$ since otherwise either $b\in
P_{a}$ or $b\notin P_{x}$ (for the latter, consider the definition of
$P_{x}$). Due to vertical maximality, $P_{a}$ meets the boundary of $T$ at
both ends. Thus $\Pi_{a}$ and $\Pi_{b}$ must together enclose some boundary
nodes of $T$, which means $T$ has a hole, a contradiction.

It remains to show that $P_{x}$ is a node separator. Assuming that there would
be a $gg^{\prime}$-path that does not intersect $P_{x}$ would again induce a
hole in $T$, since $P_{x}$ is maximal vertically connected.

######  Remark 4.38.

The portals $P_{x}$ and $P_{y}$ characterized in Definition 4.35 result in
regions consisting of nodes categorized by their location with respect to
$P_{x}$ and $P_{y}$. We obtain at most four regions. Each region is formed by
the set of nodes that are on the same side of both node separators $P_{x}$ and
$P_{y}$. Formally, we assume that nodes on the portals $P_{x}$ and $P_{y}$ are
part of all regions which they are adjacent to. On the algorithmic level, we
split $T$ at $P_{x}$ and $P_{y}$, see Figure 5 where nodes on $P_{x}$ and
$P_{y}$ are “copied” with one copy in each resulting region, as in Definition
C.11.

We identify the following easy case.

######  Fact 1.

Given a region $R$ of some grid graph $\Gamma$ that is bordered by a vertical
and horizontal gate $G,G^{\prime}$ which intersect in a node. Then there is
_no_ shortest path in $\Gamma$ between two points in $R$ that leaves and then
reenters through any of those gates as such a path can always be made shorter.
In particular, this implies that a region that has just one or at most two
gates that intersect, must be path-convex.

Another important property is the following.

######  Lemma 4.39.

Let $R$ be a path-convex region and let $P$ be a portal through $R$. If we
split $R$ at $P$ the resulting regions remain path-convex.

######  Proof 4.40.

Let $u,v\in R$ both be in one of the resulting regions after splitting at $P$.
Since $R$ was path-convex there is a shortest $uv$-path $\Pi$ inside $R$.
Assume $\Pi$ would cross $P$, i.e., leave the new region of $u,v$ and reenter
it through nods on $P$, then $\Pi$ could clearly be shortened along $P$, which
contradicts the fact that $\Pi$ is shortest.

We continue with the first step of the overall proof, namely grid nodes
$u,v\in T$ that lie on a shortest path from $g$ to $g^{\prime}$. In
particular, this means that $u,v$ are not located in “cavities” of the tunnel
region, which is a more complicated case, which we will carefully break down
into this simpler case afterwards. We start with the following technical lemma
that shows that two points that are on shortest $gg^{\prime}$-paths and on
$P_{x}$ and $P_{y}$, are relatively close. Recall that
$d_{x}:=d_{x}(g,g^{\prime})$ and $d_{y}:=d_{y}(g,g^{\prime})$.

######  Lemma 4.41.

Let $T$ be a tunnel region with two gates $g,g^{\prime}$ that are single
nodes. Let $\Pi,\Pi^{\prime}$ be two shortest $gg^{\prime}$-paths. Let $u\in
P_{x}\cap\Pi$ and $v\in P_{y}\cap\Pi^{\prime}$ (interpreting
$\Pi,\Pi^{\prime}$ as set of nodes on the path; for $P_{x},P_{y}$ see Def.
4.35). Then $d_{x}(u,v)\leq\lceil\tfrac{d_{x}}{2}\rceil$ and
$d_{y}(u,v)\leq\lceil\tfrac{d_{y}}{2}\rceil$.

color=yellow!50]Julian: a picture would probably help somewhere here (i.e.
here or at a related lemma) color=blue!40]Phil: I agree, maybe I’ll still do
one, but priority for making pictures for the appendix is low

######  Proof 4.42.

By symmetry, it suffices to prove
$d_{x}(u,v)\leq\lceil\tfrac{d_{x}}{2}\rceil$. Let $u^{\prime}\in
P_{x}\cap\Pi^{\prime}$. Since $T$ is simple, we have
$|\Pi|_{x}=|\Pi^{\prime}|_{x}=d_{x}$ by Lemma B.6. In particular,
$\Pi^{\prime}_{gu^{\prime}}=\lceil\tfrac{d_{x}}{2}\rceil$ for the sub path
from $g$ to $u^{\prime}$ (by the definition of $P_{x}$ and since
$\Pi^{\prime}_{gu^{\prime}}$ is shortest too). Furthermore, $P_{x}$ separates
$g,g^{\prime}$ by Lemma 4.36. Assume that $v$ is on the same side as $g$,
otherwise the subsequent estimations admit swapping $g$ and $g^{\prime}$. Then

$d_{x}(u,v)\leq\underbrace{d_{x}(u,u^{\prime})}_{=0\text{, as }u,u^{\prime}\in
P_{x}}\\!\\!\\!+\,d_{x}(u^{\prime},v)=\underbrace{d_{x}(u^{\prime},v)}_{\text{both
on }\Pi^{\prime}}\leq
d_{x}(u^{\prime},g)=|\Pi^{\prime}_{gu^{\prime}}|_{x}=\lceil\tfrac{d_{x}}{2}\rceil.$

Note that the requirement $v\in P_{y}$ is only needed for the proof for the
vertical distance.

The lemma above already shows that leaving $T$ is not required to get from $u$
to $v$ on some shortest path, given that both points are on shortest
$gg^{\prime}$-paths and on $P_{x}$ and $P_{y}$. We will now generalize the
latter condition for two such points within the same region of $T$ after
splitting at $P_{x},P_{y}$.

######  Lemma 4.43.

Let $T$ be a tunnel region with two gates $g,g^{\prime}$ that are single
nodes. Let $\Pi,\Pi^{\prime}$ be two shortest $gg^{\prime}$-paths. Let $u$ on
$\Pi$ and $v$ on $\Pi^{\prime}$ and $u,v\in R$ for some region $R$. Then
$d_{R,x}(u,v)\leq\lceil\tfrac{d_{x}}{2}\rceil$ and
$d_{R,y}(u,v)\leq\lceil\tfrac{d_{y}}{2}\rceil$.

######  Proof 4.44.

We show $d_{x}(u,v)\leq\lceil\tfrac{d_{x}}{2}\rceil$, the vertical distance
case is analogous. Note that $\Pi$ and $\Pi^{\prime}$ must intersect $P_{x}$
and $P_{y}$ in points $x_{1}\in P_{x}$, $y_{1}\in P_{y}$, $x_{2}\in P_{x}$ and
$y_{2}\in P_{y}$, respectively.

First we show that w.l.o.g., we can assume that $y_{1}=y_{2}$. If $y_{1}\neq
y_{2}$, then, by Lemma B.12 one of the two paths
$\Pi_{gy_{1}}\circ\overline{y_{1}y_{2}}\circ\Pi^{\prime}_{y_{2}g^{\prime}}$ or
$\Pi^{\prime}_{gy_{2}}\circ\overline{y_{2}y_{1}}\circ\Pi_{y_{1}g^{\prime}}$ is
a shortest $uv$-path as well; let this path be $\widetilde{\Pi}$. Since
$u,v\in R$ are on the same side w.r.t. the separator $P_{y}$, we have that $u$
or $v$ is on $\widetilde{\Pi}$. We replace $\Pi:=\widetilde{\Pi}$, if $u$ is
on $\widetilde{\Pi}$, or $\Pi^{\prime}:=\widetilde{\Pi}$, if $v$ is on
$\widetilde{\Pi}$. Note that the preconditions of this Lemma still hold.
Additionally we obtain the property that $\Pi$ and $\Pi^{\prime}$ both
intersect in some point $R\cap P_{y}$.

Note that, $\Pi$ and $\Pi^{\prime}$ do not enter, exit and subsequently
reenter $R$ (see Fact 1). This means that there are points $u_{1},u_{2}$,
$v_{1},v_{2}$, such that $\Pi_{u_{1}u_{2}}$ and $\Pi^{\prime}_{v_{1}v_{2}}$
stay within $R$. The points of entry and exit into $R$ can only be on
$g,g^{\prime},P_{x},P_{y}$. The only case where the two entry (or exit points)
of $\Pi,\Pi^{\prime}$ into $R$ may differ, is if they are located on $P_{x}$,
due to our previous statement and due to the fact that $g,g^{\prime}$ are
points. We will assume that $u_{1}\neq u_{2}$ is possible but $v_{1}=v_{2}$
(for instance $u_{1},u_{2}\in P_{x}$ and $v_{1},v_{2}\in P_{y}$ or
$v_{1},v_{2}=g^{\prime}$) since the following proof allows to analogously
switch roles of the point pairs. More importantly, we observe that
$d_{x}(u_{1},u_{2})=0$, meaning they are “the same” in terms of vertical
distance to other points.

We split the sub paths $\Pi_{x_{1},u_{2}}$ and $\Pi^{\prime}_{v_{1},v_{2}}$
into the following segments:

$\displaystyle|\Pi_{u_{1},u_{2}}|_{x}$ $\displaystyle=\alpha+\beta,\text{
where }\alpha:=d_{x}(u_{1},u),\beta:=d_{x}(u,u_{2})$
$\displaystyle|\Pi^{\prime}_{v_{1},v_{2}}|_{x}$
$\displaystyle=\gamma+\delta,\text{ where
}\gamma:=d_{x}(v_{1},v),\delta:=d_{x}(v,v_{2})$

Since $u_{1},v_{1}\in P_{x}$ and $v_{2},u_{2}\in P_{y}$, we can apply Lemma
4.41 thus:

$\alpha+\beta\leq\lceil\tfrac{d_{x}}{2}\rceil\text{ and
}\gamma+\delta\leq\lceil\tfrac{d_{x}}{2}\rceil$

This implies

$\alpha+\gamma\leq\lceil\tfrac{d_{x}}{2}\rceil\text{ or
}\beta+\delta\leq\lceil\tfrac{d_{x}}{2}\rceil$ (1)

as otherwise one of the inequalities of (1) would be false. If the former of
the two inequalities (1) is true then applying the triangle inequality gives

$d_{x,R}(u,v)\leq|\Pi_{u,u_{1}}|_{x}+\underbrace{d_{x}(u_{1},v_{1})}_{=0}+|\Pi_{v_{1},v}|_{x}=\alpha+\gamma\leq\lceil\tfrac{d_{x}}{2}\rceil\vspace*{-3mm}$

If the latter of inequalities (1) is true then we get

$d_{x,R}(u,v)\stackrel{{\scriptstyle
u_{2}=v_{2}}}{{\leq}}|\Pi_{u,u_{2}}|_{x}+|\Pi_{v_{2},v}|_{x}=\beta+\delta\leq\lceil\tfrac{d_{x}}{2}\rceil$

In the next stage, we show that we have path convexity for arbitrary points
$u,v$ in a given region $R$ (but still gates consist of a single node). We
will show that a shortest $uv$-path that leaves $R$ will necessarily also have
to leave $T$, and we will see that it can not be shorter than a path that
stays inside $T$, partly relying on previous lemmas. One caveat is that after
splitting the tunnel $T$ the boundaries to the outer hole can be of arbitrary
shape, in particular, we could have highly complex cavities attached to such
regions, like, e.g., spirals.

To show that such structures do not matter in terms of path convexity, we
exploit a fundamental property of grid graphs, namely that for any three of
grid nodes $a,b,v$, there is a shortest $ab$-path $\Pi$ and a point
$v^{\prime}$ on $\Pi$ such that any shortest $av^{\prime}v$\- or
$bv^{\prime}v$-path is a shortest $av$\- or $bv$-path, respectively (see
Appendix B Lemma B.16). This allows us to fall back to our previous result in
Lemma 4.43 where $u,v$ lie on shortest $gg^{\prime}$-paths.

######  Lemma 4.45.

Let $T$ be a tunnel region with two gates $g,g^{\prime}$ that are single
nodes. Let $u,v\in R$ for some region $R$ of $T$ after splitting at
$P_{x},P_{y}$. Let $\widetilde{\Pi}$ be a $uv$-path that is partially outside
of $R$. Then $|\widetilde{\Pi}|\geq d_{R}(u,v)$ (which implies path
convexity).

######  Proof 4.46.

We will prove that for any such path $\widetilde{\Pi}$ there is one that stays
within $R$ and is at most as long as $\widetilde{\Pi}$. First assume that
$\widetilde{\Pi}$ leaves $R$ but not $T$, i.e., $\widetilde{\Pi}$ has a grid
node that is not in $R$ but none that is not in $T$. This means
$\widetilde{\Pi}$ does not cross through $g$ or $g^{\prime}$. Then, by Fact 1,
there must be a shorter path that stays within $R$. Furthermore,
$\widetilde{\Pi}$ must be a simple path (no node visited twice) since
otherwise $\widetilde{\Pi}$ could be made shorter by short-cutting the loop.

This implies that if $\widetilde{\Pi}$ leaves $T$ at $g$ it can only reenter
at $g^{\prime}$ or vice versa, which is the case left to consider. Let
$\widetilde{\Pi}_{T}$ be the subpaths of $\widetilde{\Pi}$ inside $T$.
W.l.o.g., we will assume that $\widetilde{\Pi}_{T}$ connects $g$ with $u$ and
$g^{\prime}$ with $v$ (otherwise we switch the roles of $g,g^{\prime}$), we
refer to this as property (A). We show that for such $\widetilde{\Pi}$ we can
fall back on Lemma 4.45 by employing Lemma B.16 in order to prove
$|\widetilde{\Pi}|\geq d_{R}(u,v)$. Let $\Pi,\Pi^{\prime}$ be two shortest
$gg^{\prime}$-paths that are closest to $u$ and $v$, respectively, and let
$u^{\prime}$ and $v^{\prime}$ be two nodes on $\Pi,\Pi^{\prime}$ that are
closest to $u$ and $v$, respectively. By Lemma B.16 we have
$d_{T}(g,u)=|\Pi_{gu^{\prime}}|+d_{R}(u^{\prime},u)$ and
$d_{T}(g^{\prime},v)=|\Pi^{\prime}_{g^{\prime}v^{\prime}}|+d_{R}(v^{\prime},v)$.

Note that there is always some shortest $gg^{\prime}$-path that intersects
$R$. This is clear if $P_{x},P_{y}$ do not intersect, since each region of $T$
has to be crossed. If they do intersect, then by definition of $P_{x},P_{y}$
there is a shortest $gg^{\prime}$-path that crosses that intersection and thus
$R$ (note that we consider the nodes in the portals $P_{x}$ and $P_{y}$ that
delimit a region $R$ as part of that region, see Remark 4.38). Therefore, the
definition of $u^{\prime},v^{\prime}$ implies that both are in $R$. This, in
turn, implies that $P_{x}$ and $P_{y}$ are each crossed by one of the two path
segments $\Pi_{gu^{\prime}},\Pi^{\prime}_{g^{\prime}v^{\prime}}$ (could be the
same path segment for both), which by Definition 4.35 of $P_{x}$ and $P_{y}$
means that we have property (B):
$|\Pi_{gu^{\prime}}|+|\Pi^{\prime}_{g^{\prime}v^{\prime}}|\geq\lfloor\frac{d_{x}}{2}\rfloor+\lfloor\frac{d_{y}}{2}\rfloor$.

$\displaystyle|\widetilde{\Pi}_{T}|\stackrel{{\scriptstyle\text{(A)}}}{{\geq}}\hskip
7.11317pt$ $\displaystyle d_{T}(g,u)+d_{T}(g^{\prime},v)$
$\displaystyle\stackrel{{\scriptstyle\text{Lem.}\ref{lem:shortest_path_property}}}{{=}}$
$\displaystyle|\Pi_{gu^{\prime}}|+d_{R}(u^{\prime},u)+|\Pi^{\prime}_{g^{\prime}v^{\prime}}|+d_{R}(v^{\prime},v)$
$\displaystyle\stackrel{{\scriptstyle\text{(B)}}}{{=}}\hskip 7.11317pt$
$\displaystyle\lfloor\tfrac{d_{x}}{2}\rfloor+\lfloor\tfrac{d_{y}}{2}\rfloor+d_{R}(u^{\prime},u)+d_{R}(v^{\prime},v)$
$\displaystyle=\hskip 8.53581pt$
$\displaystyle\lceil\tfrac{d_{x}}{2}\rceil+\lceil\tfrac{d_{y}}{2}\rceil-\tfrac{\mathbbm{1}_{[d_{x}\text{
odd}]}+\mathbbm{1}_{[d_{y}\text{
odd}]}}{2}+d_{R}(u^{\prime},u)+d_{R}(v^{\prime},v)$
$\displaystyle\stackrel{{\scriptstyle\text{Lem.}\ref{lem:split_region_diameter_special}}}{{\geq}}$
$\displaystyle
d_{R,x}(u^{\prime},v^{\prime})+d_{R,y}(u^{\prime},v^{\prime})+d_{R}(u^{\prime},u)+d_{R}(v^{\prime},v)-\tfrac{\mathbbm{1}_{[d_{x}\text{
odd}]}+\mathbbm{1}_{[d_{y}\text{ odd}]}}{2}$
$\displaystyle\stackrel{{\scriptstyle\text{Lem.}\ref{lem:length_of_shortest_paths_in_simple_regions}}}{{=}}$
$\displaystyle
d_{R}(u^{\prime},v^{\prime})+d_{R}(u^{\prime},u)+d_{R}(v^{\prime},v)-\tfrac{\mathbbm{1}_{[d_{x}\text{
odd}]}+\mathbbm{1}_{[d_{y}\text{ odd}]}}{2}$
$\displaystyle\stackrel{{\scriptstyle\Delta\text{-ineq.}}}{{\geq}}$
$\displaystyle d_{R}(u,v)-\tfrac{\mathbbm{1}_{[d_{x}\text{
odd}]}+\mathbbm{1}_{[d_{y}\text{ odd}]}}{2}$

Note that we lower bounded the part of $\widetilde{\Pi}$ inside $T$. If $g$
and $g^{\prime}$ are distinct points then
$|\widetilde{\Pi}|\geq|\widetilde{\Pi}_{T}|+1\geq d_{R}(u,v)$. If $g$ and
$g^{\prime}$ happen to be unconnected copies of a node (see Lemma 4.29) then
any $|\widetilde{\Pi}|_{x},|\widetilde{\Pi}|_{y}$ must both be even, thus
$|\widetilde{\Pi}_{T}|\geq d_{R}(u,v)$.

Finally, we generalize our approach to handle tunnels $T$ with gates
$G,G^{\prime}$ that are vertical portals. Note that when we created the
tunnels in Section 4.2 we only used vertical gates to delimit those. Also,
note that our construction to make tunnels with single node gates path-convex
can not be used out of the box, in particular since $P_{y}$ from Definition
4.35 is no longer well defined.

We describe here two fundamental cases of the shape of $T$ and give a
construction to make convex in either case, see Figure 6.

######  Fact 2.

Let $T$ be a tunnel with gates $G,G^{\prime}$. Let $g_{1},\dots,g_{\ell}$ be
the set of nodes on $G$ from bottom to top (i.e., sorted by ascending
$y$-coordinate). Let $d(i):=d_{T,y}(g_{i},G^{\prime})$ be the vertical
distance in $T$ from $g_{i}$ to $G^{\prime}$. Consider $d(i)$ the as a
function over $i\in[\ell]$. We have intervals $[1,\ldots,i_{1}\\!-\\!1]$,
$[i_{1},\ldots,i_{2}]$ and $[i_{2}\\!+\\!1,\ldots,\ell]$ where $d(i)$ is
monotonously decreasing, assuming its minimum and monotonously increasing,
respectively. Note that the first and third interval can be empty ($i_{1}=1$
or $i_{2}=\ell$) and $i_{1}=i_{2}$ is possible, in which case we define
$i^{\prime}:=i_{1}$. This property of $d(i)$ is due to the fact that $T$ is
simple and $G$ and $G^{\prime}$ are vertical portals (our claims are
illustrated by Figure 6). We distinguish two cases

  1. (a)

$d(i)$ strictly decreases until $d(i_{1})=0$ for some $i_{1}\in[\ell]$ then
stays constant at 0 until some $i_{2}\in[\ell]$ after which $d(i)$ strictly
increases (includes $i_{1}=i_{2}$ and $d(i_{1})=0$).

  2. (b)

$d(i)$ strictly decreases until assuming an absolute minimum $d(i^{\prime})>0$
for $i^{\prime}\in[\ell]$ and then strictly increases (excludes
$d(i^{\prime})=0$).

(a)

(b)

Figure 6: Splitting tunnels into path-convex regions in two cases according to
Def. 4.47.

We split the tunnels differently depending on which case of 2 our tunnel falls
into (see Figure 6 for a visualization).

######  Definition 4.47.

Based on this case distinction in Fact 2 we make the following construction to
decompose $T$ into path-convex regions (consult Figure 6 for an illustration).

  1. (a)

Let $g_{\downarrow}:=g_{i_{1}}$ and $g_{\uparrow}:=g_{i_{2}}$. Note that we
have two nodes $g_{\downarrow}^{\prime},g_{\uparrow}^{\prime}$ on
$G^{\prime}$, that fulfill exactly the same conditions on $G^{\prime}$ as
$g_{\downarrow},g_{\uparrow}$ on $G$. The pairs are “facing” each other
horizontally, i.e., we have
$d_{y}(g_{\downarrow},g^{\prime}_{\downarrow}),d_{y}(g_{\uparrow},g^{\prime}_{\uparrow})=0$.
We split $T$ at the two horizontal portals $P_{\downarrow},P_{\uparrow}$ in
$T$ (!) between the pairs $g_{\downarrow},g_{\downarrow}^{\prime}$ and
$g_{\uparrow},g_{\uparrow}^{\prime}$ (possibly $P_{\downarrow}=P_{\uparrow}$).
Furthermore, in case $P_{\uparrow}$ touches a boundary node $b_{\uparrow}\neq
g_{\uparrow},g_{\uparrow}^{\prime}$ of a hole _above_ $P_{\uparrow}$, then we
split the region above $P_{\uparrow}$ at the leftmost such node in horizontal
direction. We do this symmetrically for the region below $P_{\downarrow}$.

  2. (b)

Let $g:=g_{i^{\prime}}$ the node on $G$ where $d(i^{\prime})$ is minimal and
let $g^{\prime}$ be the node with the same property on $G^{\prime}$. We split
$T$ at horizontal portals $P$ and $P^{\prime}$ in $T$(!) through $g$ and
$g^{\prime}$. Let $b,b^{\prime}$ be the leftmost node where $P,P^{\prime}$
touch the boundary with the hole located above $P$ or below $P^{\prime}$,
respectively. We conduct a horizontal split at $b$ and $b^{\prime}$,
respectively. Then we split $T$ at $P_{x}$, $P_{y}$ that are defined with
respect to the two nodes $g,g^{\prime}$ as in Definition 4.35.

We now prove that the regions given by the splitting procedure in Definition
4.47

We conclude with the proofs of Lemmas 4.31, 4.32 and 4.33.

######  Proof 4.48 (Proof of Lemma 4.31).

Case (b) potentially produces the most regions. $P_{x}$ intersects at most 3
horizontal portals which gives at most 8 regions. Splitting at $b,b^{\prime}$
adds at most 2 more regions.

######  Proof 4.49 (Proof of Lemma 4.32).

Case (a): In non-degenerate cases we obtain the 5 regions shown in the example
in Figure 6(a). The middle one forms a rectangle, which is clearly path-
convex. The others are bordered by at most 2 portals each, thus are path-
convex by Fact 1.

Case (b): If we disregard the split at $P_{x}$, then the regions above and
below $P$ and $P^{\prime}$ are path-convex by Fact 1. This property is
retained for the resulting regions after potentially splitting these two
regions again at $P_{x}$, by Lemma 4.39. We end up with two regions that are
bordered, only by $P$, $G$ and $P^{\prime}$, $G^{\prime}$, respectively, which
are also path-convex by Fact 1.

Let $T^{\prime}$ be the connected area that is enclosed by $P,P^{\prime}$
(such that $P_{y}$ is _inside_ $T^{\prime}$) with the nodes on the portals
$P,P^{\prime}$ part of $T^{\prime}$. The remaining area that is unaccounted
for resembles our tunnel with single node gates. In particular, for any node
pair $u,v$ inside $T^{\prime}$ any $uv$-path $\Pi$ that leaves the tunnel $T$
has to intersect $P$ _and_ $G$ when leaving $T$ and $P^{\prime}$ _and_
$G^{\prime}$ when reentering. Since $P,G$ and $P^{\prime},G^{\prime}$
intersect in $g$ and $g^{\prime}$, respectively, there is also a $uv$-path
$\widetilde{\Pi}$ that goes through $g$ and $g^{\prime}$ and is at most as
long as $\Pi$ (see Figure 6(b)).

We can therefore consider $T^{\prime}$ as tunnel region with single node gates
$g,g^{\prime}$, since these points of entry and exit suffice to obtain
shortest paths that travel outside of $T^{\prime}$. By Lemma 4.45, after
splitting at $P_{x}$ and $P_{y}$, the regions that $T^{\prime}$ decomposes
into are path-convex.

######  Proof 4.50 (Proof of Lemma 4.33).

We first invoke 3.9 for the two gates $G,G^{\prime}$, after which every node
in $T$ will know their distance to these gates. This takes $\smash{O}(\log n)$
rounds. In particular, this allows the nodes on $G$ to determine their role,
in particular, whether they are the nodes $g_{\downarrow},g_{\uparrow}$ or $g$
described in Fact 2, just by looking at the distance to $G^{\prime}$ of their
neighbors and using the properties of the distance function $d$ defined in
Fact 2. We proceed analogously for the nodes on $G^{\prime}$.

In case (a) we construct the two horizontal portals
$P_{\downarrow},P_{\uparrow}$ in $T$ with endpoints at
$g_{\downarrow},g_{\uparrow}$ using our procedures from Sections C.1 and C.2.
Using these subroutines, we can also identify the nodes
$b_{\downarrow},b_{\uparrow}$ described in case (a). We conduct a split at
$b_{\uparrow}$ on $P_{\uparrow}$ with respect to the hole above
$b_{\uparrow}$, as described in Section C.3.

Let us consider case (b). Constructing $P,P^{\prime}$ and $b,b^{\prime}$ is
analogous to case (a). Since $T$ is simple we can use Corollary C.7 and
broadcast the distances $d_{x}=d_{x,T}(g,g^{\prime})$ and
$d_{y}=d_{y,T}(g,g^{\prime})$ to all nodes in $T$. Since these also know their
horizontal and vertical distances to $G$ and $G^{\prime}$, nodes can locally
decide whether they are part of the portals $P_{x}$, $P_{y}$ (see Def. 4.35).
We have thus constructed all portals and nodes at which we want to split our
regions (meaning that all nodes know about their roles in the splitting
process). We apply the construction described in Def. C.11, where the round
complexity of $\smash{O}(\log n)$ is guaranteed by Lemma C.12.

##  5 Landmark Graph

Our next task is to provide a skeleton of the regionalization which
facilitates optimal routing. To do this, we construct what we call a _landmark
graph_. The intuition is that we mark certain gate nodes as _landmarks_ if
they are likely to appear on a shortest path between two regions, and so we
can (at least approximately) reduce the problem of finding shortest paths to
the problem of finding shortest paths between landmarks.

We connect pairs of landmarks which lie in the same region with virtual edges.
These edges have weights corresponding to the distance between the landmarks
(calculated using the SSSP subroutine developed in Section 3). We call the
resulting graph the _landmark graph_. Our goal is to distribute the landmark
graph to every node so that routing decisions can be made locally: this is
made possible by its relatively small size.

For this section, we assume that we have a grid graph $\Gamma$ which has been
regionalized by Theorem 4.3. We call this a _regionalized grid graph_ ; we
refer to the set of regions as $\mathcal{R}$. This section introduces
landmarks and presents various useful properties of them, shows that the
landmark graph is of small size, shows that shortest paths in the landmark
graph pass through the same regions as shortest paths in the underlying grid
graph, and finally demonstrates that the landmark graph can be computed
quickly.

First, we define which nodes are marked as landmarks. An example of the
placement of landmarks, colored by type, is given in Figure 7(a).

(a) An example of the placement of landmarks. Portal-end landmarks are in
orange; overhang-induced landmarks are in green; and projected landmarks are
in red.

(b) An example of a landmark path from $s$ to $t$. The Orange edges are edges
in $E_{\Lambda}$, and the green edges are composed of multiple edges in
$E_{\Gamma}$.

Figure 7: An overview of our landmark construction.

######  Definition 5.1.

Given a regionalized grid graph $\Gamma$, consider a vertex $v\in V_{\Gamma}$
which lies on a _gate_ $G$. Let $P$ be the portal perpendicular to $G$ passing
through $v$ (note that if $v$ lies at the intersection of four gates, it is a
landmark of the first type), and let $R$ be one of the regions incident to
$G$. Note that $v$ is one of the endpoints of $P\cap R$ (the portal $P$
restricted to the region $R$).

Then $v$ is a landmark if one of the following holds:

  1. i.

$v$ is an endpoint of $G$.

  2. ii.

$v$ is an overhang-induced landmark. Let $u$ be the other endpoint of $P\cap
R$. Then $v$ is an overhang-induced landmark if for some $p\in P\cap R$:

     * •

$p$ lies on a wall $W$; and

     * •

$u$ lies either on $W$ or a gate which is not $G$

We describe $p$ as an “overhang” (though note: $p$ is not marked as a
landmark).

  3. iii.

$v$ is a projection landmark: that is, if any node on $P$ is a landmark of
either of the first two types.

Next, we define the landmark graph as follows:

######  Definition 5.2.

Suppose we have a regionalized grid graph $\Gamma=(V_{\Gamma},E_{\Gamma})$
with a set of landmarks $V_{\Lambda}\subseteq V_{\Gamma}$. We define the
_landmark graph_ as $\Lambda=(V_{\Lambda},E_{\Lambda})$, where $\\{u,v\\}\in
E_{\Lambda}$ if $u,v\in V_{\Lambda}$ and either: (i) $u$ and $v$ are on the
same portal and there is no landmark between them; or (ii) $u$ and $v$ are on
different gates incident to the same region, and $v$ is the closest landmark
on its gate to $u$.

Note that we do not connect _all_ pairs of landmarks which lie in the same
region: to do so would give $|E_{\Lambda}|=\omega(|\mathcal{H}|^{2})$, and
this would adversely affect the running time. We show in Section 5.1 (Lemma
5.13) that the edges that we select are sufficient to preserve the properties
which we need. We present the following observation, which gives us that
$|E_{\Lambda}|=O(|V_{\Lambda}|)$:

5.2 has two rules adding edges to the landmark graph. The first adds edges
between adjacent landmarks on a gate. The second adds edges to the closest
point on gates bordering the same region. As each region has a constant number
of gates according to Section 6, we can conclude that each landmark has
constant degree.

Next, we define the notion of a landmark path (see also Figure 7(b)). Note
that the following definition does not require that $s$ and $t$ are landmarks,
merely vertices in the grid graph.

######  Definition 5.3.

Suppose we have a regionalized grid graph $\Gamma$ with a set
$V_{\Lambda}\subseteq V_{\Gamma}$ of landmarks and two vertices $s,t$ which
lie in different regions in $\mathcal{R}$. We define a _landmark path_ from
$s$ to $t$ as any path which goes from $s$ to some landmark $\ell_{s}$ via
edges in $E_{\Gamma}$, then goes from $\ell_{s}$ to some other landmark
$\ell_{t}$ via edges in $E_{\Lambda}$ (Definition 5.2), and then goes from
$\ell_{t}$ to $t$ via edges in $E_{\Gamma}$. We say that a landmark path
induces a sequence of regions $(R_{0},R_{1}\dots R_{m})$: these are the
regions which the underlying grid edges of the landmark path pass through, in
order.888In the special case that two consecutive regions $R_{i},R_{i+1}$ meet
at a corner, we include one of the regions which is adjacent to both $R_{i}$
and $R_{i+1}$ in the sequence, in between them.

We now give an overview of the rest of the section. In Section 5.1, we give
some miscellaneous properties of the landmark graph. In Section 5.2, we give
several lemmas relating to the routing-related properties of landmark graphs,
and we conclude with a proof of the following theorem:

######  Theorem 5.4.

Let $\Gamma$ be a regionalized grid graph with a set $V_{\Lambda}\subseteq
V_{\Gamma}$ of landmarks, and two vertices $s,t$ in different regions in
$\mathcal{R}$. Some shortest path in the grid graph from $s$ to $t$ crosses
exactly the same sequence of regions as those induced by the shortest landmark
path from $s$ to $t$.

Finally, we claim that the landmark graph is also easy to compute. In
particular, we have the following lemmas regarding its computation, which we
prove in Section 5.3.

######  Lemma 5.5.

Given a regionalized grid graph $\Gamma$, nodes can be informed whether they
are landmarks (as in Definition 5.1) in $O(\log n)$ rounds.

######  Lemma 5.6.

Given a regionalized grid graph $\Gamma$ with a set of landmarks $V_{\Lambda}$
(computed as in Lemma 5.5), the landmark graph
$\Lambda=(V_{\Lambda},E_{\Lambda})$ can be computed, such that every landmark
node knows its adjacent landmarks in $\Lambda$ in $O(\log n)$ rounds.

###  5.1 Properties of the Landmark Graph

In this section give some miscellaneous properties of landmarks, the landmark
graph, and landmark paths which will be useful in the two subsequent
subsections.

We begin with a lemma which says that, if we start at a landmark in a region
$R$, the closest point in another region (equivalently, the closest point on
another gate bounding $R$) is also a landmark. See also Figure 8 for some
visual intuition for the lemma.

######  Lemma 5.7.

Let $\Gamma$ be a regionalized grid graph with a set of landmarks
$V_{\Lambda}\subseteq V_{\Gamma}$. Let $u$ be a landmark incident to a region
$R$, and let $G$ be a gate incident to $R$, on which $u$ does not lie.

The closest vertex on $G$ to $u$ is a landmark.

######  Proof 5.8.

Suppose wlog that $G$ is horizontal and $R$ is to the north of $G$. Let
$(v_{1},v_{2}\dots v_{k})$ be the set of nodes of $G$ from left to right. For
each $v_{i}$, let $P_{i}$ denote the vertical portal on which $v_{i}$ lies,
restricted to $R$, and let $R_{V}$ denote $\bigcup P_{i}$, i.e. the union of
the vertical portals through the nodes on $G$. Let $\Pi$ denote a shortest
path from $u$ to $G$.

Observe that (i) $\Pi$ must enter $R_{V}$ (since $G\in R_{V}$), and (ii) from
the first point on $\Pi$ which lies on some portal $P_{i}\subseteq R_{V}$, the
shortest path to $G$ is along $P_{i}$.

If $u\in P_{i}$ for some $P_{i}\in R_{V}$, then, since $u$ lies on a gate (as
it is a landmark), and there is a portal connecting $u$ and $G$, either
$v_{i}$ is a landmark of the first two types, or $v_{i}$ must be a projected
landmark (case (iii) of Definition 5.1).

Otherwise $u\not\in R_{V}$. Let $q$ be the last node on $\Pi$ which is not in
$R_{V}$, and let $p\in P_{i}$ (for some $P_{i}$) be the first node which is.
It suffices to argue that $v_{i}$ is a landmark. Observe that the grid edge
from $q$ to $p$ must be horizontal (if it were vertical then clearly $q\in
P_{i}$, which is a contradiction); suppose wlog that $q$ is to the left of
$p$.
Since $q\in R_{V}$, there is some grid point which is not a grid node on the
line segment between $q$ and $G$. The grid point immediately to the right of
this grid point must be a grid node, however, since it lies on $P_{i}$: call
this node $p^{\prime}$. It is clear that $p^{\prime}$ is incident to a wall
$W$ (since the grid point to its left is unoccupied). We argue that
$p^{\prime}$ is an overhang, and that $v_{i}$ is therefore an overhang-induced
landmark (case (ii) of Definition 5.1).
Let $v^{\prime}_{i}$ be the endpoint of $P_{i}$ which is not $v_{i}$. If
$v^{\prime}_{i}$ lies on a gate, or $v^{\prime}_{i}$ is a wall of node of the
wall $W^{\prime}\neq w$ then $v_{i}$ is an overhang-induced landmark and we
are done. Suppose $v^{\prime}_{i}$ lies on $W$. Let $R^{\prime}$ be the region
bounded by $W$ and the segment of $P_{i}$ between $p^{\prime}$ and
$v^{\prime}_{i}$. Since $R^{\prime}$ contains no landmarks, $\Pi$ must have
entered this region to reach $q$ and then returned to the boundary of the
region to reach $p$. So $\Pi$ could be shortened by not entering $R^{\prime}$,
which contradicts that $\Pi$ is a shortest path.

Figure 8: A visual explanation of Lemma 5.7. Blue lines are gates, red crosses
are landmarks, and two example paths between landmarks are depicted with red
dotted lines. The bottom gate corresponds to $G$, and $R_{V}$ is denoted by a
blue shaded area. Notice that if landmarks on other gates lie inside $R_{V}$
then there must be a corresponding landmark on $G$; if landmarks on other
gates lie outside $R_{V}$ then the must enter from the left or right, and then
the shortest path is direct to $G$.

A useful corollary follows from the case distinction of this lemma:

######  Corollary 5.9.

Let $\Gamma$ be a regionalized grid graph, let $u$ be a point in a region $R$,
and let $G$ be a gate bounding $R$, on which $u$ does not lie.

If the closest vertex on $G$ to $u$ is not a landmark, the shortest path from
$u$ to $G$ is a straight line.

Next, we argue that in a simple region $R$ and given a point $u$ in $R$, it
must be the case that there’s a unique closest point to $u$ on any gate
bounding $R$. We start by giving a slightly more general lemma which then
immediately implies this.

######  Lemma 5.10.

Let $\Gamma$ be a regionalized grid graph. Let $u$ and $v$ be vertices in the
same region $R$, let $v$ lie on a gate bounding $R$ and let $v_{1}$ and
$v_{2}$ be the neighbors of $v$ on its portal. Then
$d_{\Gamma}(u,v_{1})>d_{\Gamma}(u,v)$, or
$d_{\Gamma}(u,v_{2})>d_{\Gamma}(u,v)$.

######  Proof 5.11.

Let $\Pi_{1}^{*}$ be a shortest path in $R$ from $u$ to $v_{1}$, and let
$\Pi_{2}^{*}$ be a shortest path in $R$ from $u$ to $v_{2}$. Let $p$ be the
last point that $\Pi_{1}^{*}$ and $\Pi_{2}^{*}$ have in common, when
traversing both paths from $u$ to their respective destinations, and let the
subpath of $\Pi_{1}^{*}$ starting at $p$ and ending at $v_{1}$ be $\Pi_{1}$
(resp. $\Pi_{2}$). Note that if $v$ is a point on either of $\Pi_{1}$ or
$\Pi_{2}$ we are done (as we just terminate the path in question at $v$—it
must be shorter than the full path), and so assume it is not: this implies
that the area enclosed by $\Pi_{1}$, $(v_{1},v)$, $(v,v_{2})$, and $\Pi_{2}$
is a simple cycle in the grid graph (as otherwise, $\Pi_{1}$ or $\Pi_{2}$
could be shortened).

Consider a line segment $\ell$ which starts at $v$ and extends into $R$,
perpendicular to $P_{v}$, until it intersects either $\Pi_{1}$ or $\Pi_{2}$.
Note that all points on $\ell$ are within the simple cycle formed by the paths
and vertices $v_{1},v,v_{2}$, and therefore all vertices along $\ell$ exist
(i.e. none lie within holes). Suppose without loss of generality that $\ell$
intersects $\Pi_{1}$ at point $v^{*}$, and the length of $\ell$ from $v$ to
$v^{*}$ is $x$. Now consider the path formed by concatenating the path
$\Pi^{*}_{1}$ from $u$ up to the point $v^{*}$, with the line segment $\ell$
(from $v^{*}$ to $v$). Since $d_{\Gamma}(v^{*},v_{1})\geq x+1$ but $\ell$ is
of length $x$, this path is shorter than $\Pi^{*}_{1}$ and goes from $u$ to
$v$, proving the lemma.

######  Corollary 5.12.

Let $\Gamma$ be a regionalized grid graph. Let $u$ be a vertex in a region
$R$, and let $G$ be a gate incident to $R$.

There is a _unique_ closest point to $u$ on $P$. Let this point be $v$. Given
another point $w$ on the same portal as $v$,
$d_{\Gamma}(u,w)=d_{\Gamma}(u,v)+d_{\Gamma}(v,w)$.

Next, we show that the edges that we have selected to be part of our landmark
graph are sufficient to represent shortest paths between all pairs of
landmarks which border a region.

######  Lemma 5.13.

Let $u$ and $v$ be landmarks in the same region $R$. Some shortest path in
$\Gamma$ from $u$ to $v$ can be expressed as the concatenation of the
underlying paths of edges in $E_{\Lambda}$.

######  Proof 5.14.

This follows from Lemmas 5.7 and 5.10. First, recall that since $R$ is path-
convex there exists some shortest path between $u$ and $v$ in $\Gamma$ which
lies entirely in $R$.

Let $P_{u}$ and $P_{v}$ be the portals on which $u$ and $v$ lie. If
$P_{u}=P_{v}$, then the lemma statement is trivially true, since there are
edges in $E_{\Lambda}$ between adjacent landmarks on the same portal, and the
shortest path between $u$ and $v$ is along the portal on which they both lie.

If $P_{u}\neq P_{v}$, then let $v^{*}$ be the closest point on $P_{v}$ to $u$,
which, by Lemma 5.7, is a landmark (and hence $(u,v^{*})$ is an edge in
$E_{\Lambda}$). We claim that some shortest path between $u$ and $v$ first
goes from $u$ to $v^{*}$, and then goes from $v^{*}$ to $v$ along $P_{v}$;
equivalently, $d_{\Gamma}(u,v^{*})+d_{\Gamma}(v^{*},v)=d_{\Gamma}(u,v)$. This
follows easily from Corollary 5.12, and this path can be constructed using
edges in $E_{\Lambda}$.

Finally for this section, we compute the size of the landmark graph. This will
be particularly useful when we consider the computational complexity of
distributed our landmark graph and setting up our routing scheme in Section 6.

######  Lemma 5.15.

Given a regionalized grid graph $\Gamma$ with $|\mathcal{H}|$ holes and a set
of landmarks $V_{\Lambda}$ as in Definition 5.1, the following properties all
hold:

  * •

Each landmark is adjacent to $O(1)$ regions.

  * •

Each region has $O(k)$ adjacent landmarks.

  * •

The landmark graph $\Lambda$ has $|V_{\Lambda}|=O(k^{2})$ nodes

  * •

The landmark graph has $|E_{\Lambda}|=O(k^{2})$ edges.

######  Proof 5.16.

We begin by observing that since landmarks are always placed on portals (cf.
Definition 5.1), and each portal bounds at most a constant number of regions
(follows from the splitting procedure), the first property holds.

For the second and third properties, we count the three different origins of
landmarks separately:

  * •

Endpoints of a gate: From Theorem 4.3 we know that
$|\mathcal{R}|=O(|\mathcal{H}|)$. Consider the graph where vertices are
regions and there is an edge between regions for each portal that connects
them. Clearly this graph is planar and therefore the number of portals
bounding regions is $O(|\mathcal{H}|)$ as well. Trivially, since each region
is bounded by a constant number of portals, each region has a constant number
of adjacent landmarks of this type.

  * •

Overhang-induced regions: By the definition of overhangs there can be at most
two overhang-induced landmarks for each pair of horizontal (resp. vertical)
gates bounding a region. Since the number of gates bounding a region is
constant, there are a constant number of overhang-induced portals per region,
and the total over the graph is $O(|\mathcal{H}|)$.

  * •

Projected landmarks: Clearly we must have $O(|\mathcal{H}|^{2})$ of these,
since there are $O(|\mathcal{H}|)$ overhangs in total and each could be
“projected” onto any gate bounding any other region. There are
$O(|\mathcal{H}|)$ regions and each is bounded by $O(1)$ gates, giving the
claimed bound.

The number of landmark edges in each region is $O(|\mathcal{H}|)$, as by
Section 5 each landmark has at most a constant number of neighbours in each
region. Since there are $O(|\mathcal{H}|)$ regions, the bound in the fourth
property follows immediately.

###  5.2 Routing Properties of the Landmark Graph

Next, we show that our choice of where to place landmarks give us useful
properties for routing. We conclude the section with the proof of Theorem 5.4.

First, we show that, if we fix a sequence of regions through which a path must
travel, a shortest path can be obtained by repeatedly routing to the closest
point in the next region in the sequence.

######  Lemma 5.17.

We say that an $s$-$t$ path is _shortest-possible_ relative to a sequence of
pairwise-adjacent regions $(R_{0},R_{1},\dots R_{m})$, where $s\in R_{0}$ and
$t\in R_{m}$, if no shorter path passes through exactly those regions, in
order.

A shortest-possible $s$-$t$ path can be obtained by routing from $s$ to the
closest point in $R_{1}$, then to the closest point in $R_{2}$, and so on: and
when finally $R_{m}$ is entered, taking a shortest path to $t$.

######  Proof 5.18.

Let $\Pi^{*}$ be a shortest-possible path from $s$ to $t$, and let $\Pi$ be a
path which follows the strategy outlined in the lemma. We will show that
$|\Pi|=|\Pi^{*}|$. We will notate the length of path $\Pi$ between points $x$
and $y$ as $|\Pi(x,y)|$ (and analogously for the length of $\Pi^{*}$).

Suppose for each $R_{i}$, $\Pi^{*}$ enters $R_{i}$ at some point $v^{*}_{i}$,
and $\Pi$ enters $R_{i}$ at $v_{i}$. Note that since pairs of adjacent regions
are connected by a single portal, $v_{i}$ and $v^{*}_{i}$ are on the same
portal. It suffices to show that
$|\Pi^{*}(s,v^{*}_{m})|=|\Pi(s,v_{m})|+d_{\Gamma}(v_{m},v^{*}_{m})$, since
when routing to $t$ in the final step, clearly $d_{\Gamma}(v_{m},t)\leq
d_{\Gamma}(v_{m},v^{*}_{m})+d_{\Gamma}(v^{*}_{m},t)$ (as we can route via
$v^{*}_{m}$ if this is shortest).

We prove this by induction. Note that as a consequence of Corollary 5.12, we
have that $|\Pi^{*}(s,v^{*}_{1})|=|\Pi(s,v_{1})|+d_{\Gamma}(v_{1},v^{*}_{1})$,
hence the base case is satisfied. Now by two applications of Corollary 5.12 we
have, for all $v_{i},v_{i+1},v^{*}_{i},v^{*}_{i+1}$, a kind of rectangle
equality:

$d_{\Gamma}(v_{i},v_{i+1})+d_{\Gamma}(v_{i+1},v^{*}_{i+1})=d_{\Gamma}(v_{i},v^{*}_{i})+d_{\Gamma}(v^{*}_{i},v^{*}_{i+1})$

And this gives us:

$\displaystyle|\Pi^{*}(s,v^{*}_{i+1})|$
$\displaystyle=|\Pi^{*}(s,v^{*}_{i})|+d_{\Gamma}(v^{*}_{i},v^{*}_{i+1})$
$\displaystyle=|\Pi(s,v_{i})|+d_{\Gamma}(v_{i},v^{*}_{i})+d_{\Gamma}(v^{*}_{i},v^{*}_{i+1})$
$\displaystyle=|\Pi(s,v_{i})|+d_{\Gamma}(v_{i},v_{i+1})+d_{\Gamma}(v_{i+1},v^{*}_{i+1})$
$\displaystyle=|\Pi(s,v_{i+1})|+d_{\Gamma}(v_{i+1},v^{*}_{i+1})$

as required.

Next, we show that if _any_ shortest path between two nodes contains a
landmark, then there is a shortest path between those two nodes which is a
landmark path.

######  Lemma 5.19.

If there is a landmark on some shortest path in the grid graph from $s$ to
$t$, then some shortest path in the grid graph from $s$ to $t$ is a landmark
path.

######  Proof 5.20.

Firstly, note that if $v$ is a point on a shortest $st$-path, then this
shortest $st$-path is composed of a shortest $sv$-path and a shortest
$vt$-path.

Then, consider a landmark $\lambda$ on a shortest $st$-path $\Pi$, and let
$\Pi_{\lambda t}$ be the subpath of $\Pi$ from $\lambda$ to $t$. We can
replace this subpath by a new path $\Pi^{*}_{\lambda t}$ obtained by the
strategy given in Lemma 5.17, using the regions passed through by
$\Pi_{\lambda t}$ to ensure the cost does not increase relative to
$\Pi_{\lambda t}$. Note that our path starts at a landmark: by Lemma 5.7, each
time we route to the closest point in the next region in the sequence, this
point must also be a landmark. As Lemma 5.13 shows that we can replace
shortest paths between landmarks by edges in $E_{\Lambda}$, we can see that
our path $\Pi^{*}_{\lambda t}$ is a landmark path.

We can apply the same construction to replace $\Pi_{s\lambda}$ with a landmark
path $\Pi^{*}_{s\lambda}$, and finally it is easy to see that concatenating
$\Pi^{*}_{s\lambda}$ with $\Pi^{*}_{\lambda t}$ gives a landmark path of no
greater length than $\Pi$: that is to say, this landmark path is a shortest
$st$-path in the grid graph.

Figure 9: An example of the case where there are no landmarks on a shortest
path from $s$ to $t$.

We conclude the subsection with the proof of Theorem 5.4, that the shortest
$st$-landmark path crosses the same sequence of regions as a shortest
$st$-path:

######  Proof 5.21 (Proof of Theorem 5.4).

First, note that if any shortest $s$-$t$ path contains a landmark, then by
Lemma 5.19 we are immediately done.

Suppose no shortest $s$-$t$ path contains a landmark, and fix an arbitrary
shortest path $\Pi^{\prime}$. Let $\Pi$ be a shortest-possible path relative
to the same sequence of regions $(R_{1},R_{2},\dots R_{m})$ induced by
$\Pi^{\prime}$. By Lemma 5.17, we can construct $\Pi$ such that it is
comprised of a shortest path from $s$ to the region $R_{1}$, followed by a
shortest path to the region $R_{2}$, etc., when the path enters $R_{m}$, it is
then followed by a shortest path to $t$.

We now argue that, since $\Pi$ does not pass through any landmarks, it must
have a very specific structure. For each $R_{i}$, let $v_{i}$ be the first
node on $\Pi$ in $R_{i}$. Since $\Pi$ does not contain a landmark by
assumption, by Corollary 5.9 the shortest path from $s$ to $v_{1}$ must be a
straight line. This logic also applies to the shortest path from $v_{1}$ to
$v_{2}$, and from $v_{2}$ to $v_{3}$, all the way to $v_{m}$, and note further
that all of the portals on which the $v_{i}$ lie must be parallel to each
other (if the path were to “turn” between some $v_{i}$ and $v_{i+1}$, it would
necessarily reach a landmark by contrapositive of Corollary 5.9). Finally, let
the closest point to $t$ on the gate separating $R_{m-1}$ from $R_{m}$ be
$t^{*}$. A shortest path from $v_{m}$ to $t$ may go via $t^{*}$ first (by
Lemma 5.12). To summarise: $\Pi$ consists of a straight line from $s$ to
$v_{m}$, and then a path from $v_{m}$ to $t$ (via $t^{*}$).

It remains to show that the shortest landmark path induces the same sequence
of regions. Suppose without loss of generality that the gates which $\Pi$
crosses are all vertical, and let $\lambda^{\uparrow}_{i}$ and
$\lambda^{\downarrow}_{i}$ be the closest landmarks above and below $v_{i}$ on
its gate, respectively. We first argue that all of the
$\lambda^{\uparrow}_{i}$ lie in a horizontal line (and that all points along
this line are vertices in the grid graph). We argue that the shortest path
between $\lambda^{\uparrow}_{1}$ and $\lambda^{\uparrow}_{2}$ is a straight
line: the argument applies analogously to all other $\lambda^{\uparrow}_{i}$
and all $\lambda^{\downarrow}_{i}$. Let $v^{i}_{1}$ be the vertex $i$ steps
north of $v_{1}$. Iteratively consider the sequence of pairs of points
$((v^{1}_{1},v^{1}_{2}),(v^{2}_{1},v^{2}_{2})\dots)$. If any of the points on
the line between $v^{i}_{1}$ and $v^{i}_{2}$ are incident to a hole boundary,
then $v^{i}_{1}=\lambda^{\uparrow}_{1}$ and $v^{i}_{2}=\lambda^{\uparrow}_{2}$
(by case (ii) of Definition 5.1: the points are landmarks). Otherwise, suppose
that (without loss of generality), $v^{i}_{1}=\lambda^{\uparrow}_{1}$. Then,
by case (iii) of Definition 5.1, $v^{i}_{2}=\lambda^{\uparrow}_{2}$ (by
projection). If neither of these hold, then proceed to
$(v^{i+1}_{1},v^{i+1}_{2})$. Eventually the end of one of the portals will be
reached and both landmarks will be found at the same “height”.

We claim that $t$ is neither more north than $\lambda^{\uparrow}_{m}$ nor more
south than $\lambda^{\downarrow}_{m}$. To see why, recall that $t^{*}$ is the
closest point to $t$ on the gate containing $v_{m}$. If there was a landmark
between $t^{*}$ and $v_{m}$ on their gate, it would lie on $\Pi$, which is a