The University of
Sydneyjoachim.gudmundsson@sydney.edu.auhttps://orcid.org/0000-0002-6778-7990
Funded by the Australian Government through the Australian Research Council
DP180102870. The University of
Sydneyzijin.huang@uni.sydney.edu.auhttps://orcid.org/0000-0003-3417-5303 The
University of
Sydneyandre.vanrenssen@sydney.edu.auhttps://orcid.org/0000-0002-9294-9947 The
University of Copenhagensawo@di.ku.dkhttps://orcid.org/0000-0003-3803-3804

###### Acknowledgements.

Joachim Gudmundsson, Zijin Huang, André van Renssen and Sampson Wong Theory of
computation Computational geometry

# Spanner for the $0/1/\infty$ weighted region problem

Joachim Gudmundsson  Zijin Huang  André van Renssen  Sampson Wong

(October 2022)

###### Abstract

We consider the problem of computing an approximate weighted shortest path in
a weighted subdivision, with weights assigned from the set $\\{0,1,\infty\\}$.
We present a data structure $\mathcal{B}$, which stores a set of convex, non-
overlapping regions. These include zero-cost regions (0-regions) with a weight
of $0$ and obstacles with a weight of $\infty$, all embedded in a plane with a
weight of $1$. The data structure $\mathcal{B}$ can be constructed in expected
time $O(N+(n/\varepsilon^{3})(\log(n/\varepsilon)+\log N))$, where $n$ is the
total number of regions, $N$ represents the total complexity of the regions,
and $1+\varepsilon$ is the approximation factor, for any $0<\varepsilon<1$.
Using $\mathcal{B}$, one can compute an approximate weighted shortest path
from any point $s$ to any point $t$ in
$O(N+n/\varepsilon^{3}+(n/\varepsilon^{2})\log(n/\varepsilon)+(\log
N)/\varepsilon)$ time. In the special case where the 0-regions and obstacles
are polygons (not necessarily convex), $\mathcal{B}$ contains a
$(1+\varepsilon)$-spanner of the input vertices.

###### keywords:

weighted region problem, approximate shortest path, spanner

##  1 Introduction

The Weighted Region Problem (WRP) is a generalization of the shortest path
problem, considering a planar subdivision $E$ where each face has a non-
negative weight associated with it. A path $\sigma$ in $E$ can be partitioned
into a set of subpaths $\\{\sigma_{1},...,\sigma_{k}\\}$ based on its
intersection with faces in $E$, where a subpath $\sigma_{i}$ starts at the
point $s_{i}$ and ends at the point $t_{i}$. Both $s_{i}$ and $t_{i}$ must lie
on the boundary of the same face $F_{i}$. The weight of the subpath
$\sigma_{i}$ is the Euclidean length of $\sigma_{i}$ times the weight assigned
to $F_{i}$. The total weight of a path is the sum of the weights of its
subpaths. The goal of the WRP is to find the weighted shortest path from a
source point $s$ to a target point $t$. When the weights are in the set
$\\{0,1,\infty\\}$, this problem is referred to as the $0/1/\infty$ Weighted
Region Problem [17].

Researchers have conjectured that the WRP is difficult to solve [17], and
recent studies confirm this conjecture — the Weighted Region Problem is
unsolvable in the algebraic computation model over the rational numbers. De
Carufel et al. [14] demonstrated that the WRP cannot be solved exactly even
with only three different weights. De Berg et al. [12] confirmed its
unsolvability with just two different weights. Mitchell and Papadimitriou [21]
illustrated that in two dimensions, a weighted shortest path can intersect at
least $\Omega(n^{2})$ boundaries even when the regions are convex.

Due to the difficulty of solving the WRP exactly, approximation algorithms
have been considered. A common approach is to discretize the problem space,
either by assuming the space is a tessellation of convex polygons with exactly
one associated weight [5], or by placing Steiner (sample) points on the
boundaries of the regions [1, 2, 9, 20, 23]. In these approaches, the number
of sample points depends not only on the complexity of the regions but also on
geometric parameters such as the maximum integer coordinate of any vertex and
the ratio $r_{w}$ of the maximum weight over the minimum weight. As $r_{w}$
increases, so does the number of required sample points. As a result, the
weights are required to be strictly positive.

###  1.1 Related work

Our work is closely related to the data structure and algorithm by Gewali et
al. [17] to solve the $0/1/\infty$ weighted region problem. Their algorithm
takes a polygonal domain with $N$ vertices as input and constructs a _critical
graph_ $\mathcal{G}^{*}=(\mathcal{V}^{*},\mathcal{E}^{*})$ (a type of
visibility graph) with $O(N^{2})$ edges. Dijkstra’s shortest path algorithm
can be used on $\mathcal{G}^{*}$ to compute a weighted shortest path between
any pair of vertices in $O(N^{2})$ time.

In $0/1/\infty$ weighted regions, a weighted shortest path $P^{*}$ avoids
obstacles and traverses the 0-regions freely, while minimizing its length in
the plane ($1$-region). Consider two (closed) regions $A$ and $B$, each either
a 0-region or an obstacle. The key observation in [17] is that an edge in
$P^{*}$ connecting $A$ and $B$ must be _locally optimal_ (see Fact 2). For
example, an edge $(a,b)$ connecting two convex 0-regions $A$ and $B$ must be
perpendicular to the tangent touching $a\in A$ and the tangent touching $b\in
B$. Gewali et al. [17] showed that $G^{*}$ contains all such locally optimal
edges in $G^{*}$, which implies that $G^{*}$ must contain the optimal path
between any pair of vertices in $G^{*}$.

###  1.2 Our Contribution

In this paper, we build on the work by Gewali et al. [17] with a focus on the
$0$-regions as they are not handled well by existing approximation schemes
(using sample points or tessellation). In Section 2, we consider the $0/1$
weighted region problem where the 0-regions are convex but not necessarily
polygonal.

######  Problem 1.

In the planar subdivision induced by the plane with weight $1$ and a set
$\mathcal{Z}$ of non-overlapping convex zero-cost regions (0-regions) with
weight $0$, given an approximation error $0<\varepsilon<1$, find a
$(1+\varepsilon)$-approximate weighted shortest path from an arbitrary point
$s$ to an arbitrary point $t$.

The high-level idea is that, in order to obtain $(1+\varepsilon)$-approximate
shortest paths, we place $O(1/\varepsilon)$ sample points on the boundary of
each $0$-region; the number of sample points is independent of other
parameters. Using these sample points, we construct a $\Theta$-graph and
$O(1/\varepsilon)$ trapezoidal maps, which are part of our data structure
$\mathcal{B}$. The trapezoidal maps ensure the existence of good paths between
$0$-regions that are close111A precise definition is provided in Lemma 2.4 and
2.8, Section 2. to each other, while the $\Theta$-graph ensures the same for
$0$-regions that are far from each other. To the best of our knowledge, our
algorithm is the first near-linear time $(1+\varepsilon)$-approximation
algorithm that finds an approximated weighted shortest path in a $0/1$
weighted region. Our algorithm is near-optimal, as a weighted shortest path
can have $\Omega(n+N)$ complexity.

######  Theorem 1.1.

Consider a planar subdivision induced by a plane with weight 1, containing a
set $\mathcal{Z}$ of non-overlapping convex 0-regions with weight 0. Let
$|\mathcal{Z}|=n$ and $N$ denote the total number of vertices in
$\mathcal{Z}$. For any approximation factor $0<\varepsilon<1$, a data
structure $\mathcal{B}$ can be constructed over $\mathcal{Z}$ in
$O(N+(n/\varepsilon^{2})(\log(n/\varepsilon)+\log N))$ expected time, with a
total size of $O(N+n/\varepsilon^{2})$. When queried with points $s$ and $t$,
$\mathcal{B}$ can return a weighted path $P$ from $s$ to $t$ in
$O(N+n/\varepsilon^{2}+(n/\varepsilon)\log(n/\varepsilon)+(\log
N)/\varepsilon)$ time, satisfying
$\textbf{w}(P)\leq(1+\varepsilon)\cdot\textbf{w}(P^{*})$, where $P^{*}$ is the
optimal weighted shortest path from $s$ to $t$.

To use our algorithm on an application, we proved the above theorem in a more
general setting, where the 0-regions are non-polygonal. In Section 3, we use
our algorithm to approximate the partial weak Fréchet similarity of two
polygonal curves. This problem was first studied by Buchin et al. [7], and
they presented a cubic time algorithm. De Carufel et al. [13] later
transformed the problem into a weighted shortest path problem amidst
$0/1$-regions. Using Theorem 1.1, our algorithm is the first near-quadratic
time $(1+\varepsilon)$-approximation algorithm for computing the partial weak
Fréchet similarity between a pair of polygonal curves.

Buchin et al. [8] showed that there is no strongly subquadratic time algorithm
for approximating the weak Fréchet distance within a factor less than 3 unless
the strong exponential-time hypothesis fails. Approximating the partial weak
Fréchet similarity is at least as hard as approximating the weak Fréchet
distance. As a result, it is unlikely that a subquadratic time algorithm
exists, and our algorithm is near-optimal.

######  Theorem 1.2.

One can approximate the partial weak Fréchet similarity of two curves with
respect to the $L_{2}$ metric within a factor of $(1+\varepsilon)$ in
$O((n^{2}/\varepsilon^{2})\log(n/\varepsilon))$ expected time.

In Section 4, we generalise our data structure to also allow convex obstacles
that cannot be traversed, i.e., obstacles of weight $\infty$. By introducing
additional sample points, we show that if we need to take a detour from a
sample point $a$ to a sample point $b$, there exists a set $D$ (a detour) of
edges in $\mathcal{B}$ such that the total length of $D$ approximates the
distance $\textbf{d}(a,b)$ within a factor of $1+\varepsilon$. In the special
case that the 0-regions and obstacles are polygonal, $\mathcal{B}$ is a
$(1+\varepsilon)$-spanner of the input vertices. To the best of our knowledge,
our algorithm is the first near-linear time $(1+\varepsilon)$-approximation
algorithm for the weighted shortest path in a $0/1/\infty$ weighted region.

######  Theorem 1.3.

Consider a planar subdivision induced by a plane with a weight of $1$,
consisting of two sets of convex and non-overlapping regions: 0-regions
$\mathcal{Z}$ with a weight of $0$, and obstacles $\mathcal{O}$ with a weight
of $\infty$. Let $n=|\mathcal{Z}|+|\mathcal{O}|$ and let $N$ denote be the
total number of vertices in $\mathcal{Z}\cup\mathcal{O}$. For any
approximation factor $0<\varepsilon<1$, a data structure $\mathcal{B}$ can be
constructed over $\mathcal{Z}\cup\mathcal{O}$ in
$O(N+(n/\varepsilon^{3})(\log(n/\varepsilon)+\log N))$ expected time, with a
total size of $O(N+n/\varepsilon^{3})$. When queried with arbitrary points $s$
and $t$, $\mathcal{B}$ returns a weighted path $P$ from $s$ to $t$ in
$O(N+n/\varepsilon^{3}+(n/\varepsilon^{2})\log(n/\varepsilon)+(\log
N)/\varepsilon)$ time, ensuring that
$\textbf{w}(P)\leq(1+\varepsilon)\cdot\textbf{w}(P^{*})$, where $P^{*}$ is the
optimal weighted shortest path from $s$ to $t$.

##  2 Shortest path amidst 0-regions

The exact version of Problem 1 has a brute-force solution. Given two 0-regions
$A$ and $B$, where $s$ and $t$ are considered 0-regions with no interior, let
$\textbf{d}(A,B)$ be the Euclidean distance between $A$ and $B$. Let
$\mathcal{G}_{c}=(\mathcal{V},\mathcal{E}_{c})$ be a complete graph, where
$\mathcal{V}=\mathcal{Z}\cup\\{s,t\\}$. For each edge
$(A,B)\in\mathcal{E}_{c}$ for all pairs of $A\in\mathcal{V}_{c}$ and
$B\in\mathcal{V}_{c}$, set the weight $\textbf{w}(A,B)=\textbf{d}(A,B)$. Then,
finding the optimal path $P^{*}$ from $s$ to $t$ is equivalent to finding a
weighted shortest path $P^{*}$ in $\mathcal{G}_{c}$, which can be solved using
Dijkstra’s shortest path algorithm. However, the total number of edges
required is at least $\Omega(n^{2})$.

To compute an approximate solution, the goal is to construct an undirected
weighted graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, with a near-linear
number of edges, such that there exists a path $P$ in $\mathcal{G}$ with
$\textbf{w}(P)\leq(1+\varepsilon)\cdot\textbf{w}(P^{*})$.

To this end, we will use two data structures: trapezoidal maps and
$\Theta$-graphs. Both data structures are used to determine which pairs of
0-regions are connected. The trapezoidal maps will ensure that there exist
good paths between 0-regions that are close to each other, while the
$\Theta$-graph ensures the same for $0$-regions that are far from each other.

###  2.1 Construction of the data structure

In order to define our data structure, we first define a set of directions.
Let $\theta<\pi/6$ be a fixed positive real number. Let $r(k\theta)$ be the
direction with a counter-clockwise angle of $k\theta$ with the positive
$x$-axis. Let $r(p,k\theta)$ be the ray originating from the point $p$ with a
counter-clockwise angle of $k\theta$ with the positive $x$-axis. For
simplicity, we write $r(k)=r(k\theta)$ and $r(p,k)=r(p,k\theta)$. To simplify
the discussion, we will assume that $(\pi/2)/\theta\in\mathbb{Z}$ to guarantee
that if $r(k)$ exists, then so does $r(k\theta+\pi/2)$.

For a 0-region $A$, we define a set $\mathcal{SP}(A)$ of sample points on the
boundary of $A$. Let $sp(A,k\theta)=sp(A,k)$ be a sample point on the boundary
$\partial A$ of $A$ such that $sp(A,k)$ is extreme in the direction $r(k)$
(see Figure 1). When the geometric region $A$ is clear from context, we write
$sp(k)$ instead of $sp(A,k)$.

Figure 1: The sample points that are extreme in the directions of $r(k)$ and
$r(k\theta+\pi)$ are marked with black dots. The sample points that are
extreme in the directions of $r(k\theta\pm\pi/2)$ are marked with circles.
Using these sample points, we generate a simplified polygon and construct
$\mathcal{M}(k)$; the blue and green regions are examples of faces in
$\mathcal{M}(k)$.

Each 0-region $A$ is considered an open set, i.e., if $p\in\partial A$, then
$p\notin A$. Let $\partial A(a,a^{\prime})$ define the subset of $\partial A$
traversed from point $a$ to point $a^{\prime}$ in counter-clockwise order,
where $a,a^{\prime}\in\partial A$. We say a line $l$ _overlaps_ $A$ if $l$ and
$A$ intersect at more than one point. We say two regions, $A$ and $B$, are
non-overlapping if their interiors do not intersect.

A point $p\in\partial A$ can be an extreme point for more than one direction,
in which case we call $p$ a vertex of $A$. There may be more than one extreme
point on $A$ for a single direction. If $p$ is the extreme point on $A$ for
consecutive directions $\\{r(k),r(k+1),...,r(k+m)\\}$, we say $p=sp(k)$,
$p=sp(k+1)$, …, and $p=sp(k+m)$ simultaneously. If there is more than one
extreme point for a single direction $r(k)$, these extreme points must lie on
some segment $ab\subseteq\partial A$, and we say both $a$ and $b$ are $sp(k)$.
The sample points on the boundary of a convex region can be computed by
traversing the boundary.

Given $n$ convex regions with $N$ vertices in total, there are $O(n/\theta)$
sample points, and it takes $O(N+n/\theta)$ time to compute them.

Using the sample points on a 0-region $A$, we can generate a simplified
$0$-region (a convex polygon) $\mathtt{simpl}(A)$ by connecting adjacent
sample points of every 0-region (see Figure 1). Using the set
$\mathtt{simpl}(\mathcal{Z})$ of simplified 0-regions, we will generate a set
of trapezoidal maps, and we say $\mathtt{simpl}(A)$ and $\mathtt{simpl}(B)$
are adjacent if they are both adjacent to the same face in a trapezoidal map.
We construct the query data structure $\mathcal{B}$ using Algorithm 1.

Algorithm 1 Construct $\mathcal{B}$ with 0-regions

This algorithm takes as input a set $\mathcal{Z}$ of non-overlapping and
convex 0-regions, and constructs a data structure $\mathcal{B}$. The
undirected graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ is initially empty.

  1. 1.

Compute the sample points $\mathcal{SP}(\mathcal{Z})$, and add
$\mathcal{SP}(\mathcal{Z})$ to $\mathcal{V}$.

  2. 2.

Pick an arbitrary sample point as the anchor $ak(A)$ for every
$A\in\mathcal{Z}$. For each $p\in\mathcal{SP}(A)$, add $e=(p,ak(A))$ to
$\mathcal{E}$, and set $\textbf{w}(e)=0$.

  3. 3.

For each direction $r(k)$, generate a trapezoidal map $\mathcal{M}(k)$ using
$\mathtt{simpl}(\mathcal{Z})$, and do the following for each $\mathcal{M}(k)$
(see [11, Theorem 6.3 and 6.8] for trapezoidal map construction).

     * •

For each face $F\in\mathcal{M}(k)$ adjacent to $A$ and $B$, $A\neq B$, add
$e=(ak(A),ak(B))$ to $\mathcal{E}$, and set $\textbf{w}(e)=\textbf{d}(A,B)$.

  4. 4.

With $\mathcal{V}$ as the input, generate a $\Theta$-graph
$\mathcal{G}_{\Theta}=(\mathcal{V},\mathcal{E}_{\Theta})$.

     * •

For each edge $(p,q)\in\mathcal{E}_{\Theta}$, if $p$ and $q$ do not belong to
the same 0-region, add $e=(p,q)$ to $\mathcal{E}$, and set
$\textbf{w}(e)=\lVert pq\rVert$.

  5. 5.

Return $\mathcal{B}=\\{\mathcal{M}(k)\mid\forall
k\in[0,2\pi/\theta),k\in\mathbb{Z}\\}\cup\\{\mathcal{G},\mathcal{G}_{\Theta}\\}$
as the data structure.

####  2.1.1 Analysis

We bound the size of the data structure $\mathcal{B}$ and its construction
time. In Step 1, by Observation 2.1, it takes $O(N+n/\theta)$ time to compute
all $O(n/\theta)$ sample points. Step 2 takes $O(n/\theta)$ time to connect
every sample point to its respective anchor. In Step 3, it takes
$O((n/\theta^{2})\log(n/\theta))$ expected time [11] to build the trapezoidal
map $\mathcal{M}(k)$ over $\mathtt{simpl}(\mathcal{Z})$ for each of the
$O(1/\theta)$ directions. In every $\mathcal{M}(k)$, we construct at most
three edges in $\mathcal{E}$ per sample point $a=sp(A,k\theta+\pi/2)$, if
$r(a,k)$ and $r(a,k\theta+\pi)$ hit different 0-regions. Therefore
$|\mathcal{M}(k)|\in O(n/\theta)$, and in total
$\sum\limits_{k}\mathcal{M}(k)=O(n/\theta^{2})$. Once $\mathcal{M}(k)$ is
constructed for all $k$, using the algorithm by Edelsbrunner [15], it takes
$O(\log N)$ time to compute the shortest distance between two convex 0-regions
for each of the $O(n/\theta^{2})$ faces. In Step 4, it takes
$O((n/\theta^{2})\log(n/\theta))$ time to construct a $\Theta$-graph using
$O(n/\theta)$ sample points, and $O(1/\theta)$ cones [22]. Step 4a takes
$O(n/\theta^{2})$ time, since $|\mathcal{E}_{\Theta}|=O(n/\theta^{2})$.

Later, we will show that for an approximation factor $\varepsilon$, we have
that $\theta\in O(\varepsilon)$. The resulting complexities are summarised
below.

######  Lemma 2.1.

Given an approximation factor $0<\varepsilon<1$, and $n$ non-overlapping
convex 0-regions with total complexity $N$, one can build the data structure
$\mathcal{B}$ in $O(N+(n/\varepsilon^{2})(\log(n/\varepsilon)+\log N))$ time,
and the total size of $\mathcal{B}$ is $O(N+n/\varepsilon^{2})$.

To the best of our knowledge, constructing a trapezoidal map using arcs has
not been studied before. Therefore, in Algorithm 1, we used the well-studied
result on the trapezoidal map construction using segments.

For each direction $r(k)$, we built a trapezoidal map $\mathcal{M}(k)$ using
the simplified 0-regions $\mathtt{simpl}(\mathcal{Z})$, see Step 3 of
Algorithm 1. Consider the union of $\mathcal{Z}$ and
$\mathtt{simpl}(\mathcal{Z})$. We argue that constructing a trapezoidal map
using the simplified regions captures the structure of the trapezoidal map if
we had used the subboundaries of the original regions instead. To do this, we
show that if a ray $r=r(p,k)$ originating from a sample point $p$ on 0-region
$A$ hits a subboundary $\partial B(u,v)$ first, then $r$ must hit the segment
$uv$ next.

First, the 0-regions are non-overlapping, so $A$ cannot intersect the region
enclosed by $\partial B(u,v)$ and $uv$. Second, without loss of generality,
let $r(p,k)$ coincide with the $y$-axis. By construction, if $r(k)$ exists,
then $r(k\theta+\pi/2)$ and $r(k\theta-\pi/2)$ exist, which implies that there
exist two sample points: one is the leftmost point of $A$, and one is the
rightmost. Therefore, the horizontal span of $\partial B(u,v)$ and $uv$ are
equal. A ray shooting in the direction $r(k)$ cannot hit $\partial B(u,v)$
first but misses $uv$.

If a ray $r=r(p,k)$ hits a subboundary $\partial A(u,v)$ first, then $r$ must
hit $uv$ next.

With the data structure defined, we analyse the quality of the path we obtain
from $\mathcal{B}$.

###  2.2 Trapezoidal map

Before arguing that there exists a good path using the edges constructed, we
start with an observation about the pair of points realising the shortest
distance between two 0-regions. For a convex region $A$ and a point
$p\in\partial A$, there exists at least one supporting line $l=l_{t}(A,p)$
going through $p$ such that $A$ lies entirely in one of the two halfplanes
determined by $l$ [24]. Let $p\in\partial A$, and $q\in\partial B$. We can
observe that if $pq$ realises $\textbf{d}(A,B)$, then $pq$ must be
perpendicular to a pair of supporting lines $l_{t}(A,p)$ and $l_{t}(B,q)$.

Let $A$ and $B$ be two convex regions. Let $pq$ be the line segment realising
$\textbf{d}(A,B)$, where $p\in A$ and $q\in B$. The segment $pq$ must be
perpendicular to a pair of supporting lines $l_{t}(A,p)$ and $l_{t}(B,q)$.

We will show that if $pq$ realises the distance between two 0-regions, we can
transform $pq$ into another segment $pq^{\prime}$ such that $pq^{\prime}$ is
parallel to some direction $r(k)$, and $\lVert pq^{\prime}\rVert$ approximates
$\lVert pq\rVert$. To do this, we first need a fact (see Appendix
LABEL:app:lemma_rotation for a proof).

######  Lemma 2.2.

Given a segment $pq$, let $\alpha$ (resp. $\beta$) be the acute angle between
$pq$ and $r(p,k+1)$ (resp. $r(p,k)$), where $\alpha+\beta=\theta<\pi/6$. Let
$q^{\prime}$ be the intersection of $r(p,k+1)$ and $r(q,k\theta+\pi/2)$. We
have that $\lVert
pq^{\prime}\rVert=\mathchoice{\frac{\cos(\beta)}{\cos(\theta)}}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}\cdot\lVert
pq\rVert$, and $\lVert
qq^{\prime}\rVert=\mathchoice{\frac{\sin(\alpha)}{\cos(\theta)}}{(\sin(\alpha)/\cos(\theta))}{(\sin(\alpha)/\cos(\theta))}{(\sin(\alpha)/\cos(\theta))}\cdot\lVert
pq\rVert$.

######  Proof 2.3.

Figure 2: The construction in Lemma 2.2. The segment $\lVert pq\rVert$ lies
between two directions, and $\alpha$ and $\beta$ are the respective angles,
where $\alpha+\beta=\theta<\pi/6$

See Figure 2 for the construction. By the law of sines, we have

$\displaystyle\frac{\lVert
pq^{\prime}\rVert}{\sin(\measuredangle{pqq^{\prime}})}=\frac{\lVert
pq\rVert}{\sin(\measuredangle{pq^{\prime}q})}\implies\lVert
pq^{\prime}\rVert=\sin(\measuredangle{pqq^{\prime}})\cdot\frac{\lVert
pq\rVert}{\sin(\measuredangle{pq^{\prime}q})}.$

Filling in our angles, we get

$\displaystyle\lVert pq^{\prime}\rVert=\frac{\sin(\frac{\pi}{2}+\beta)\lVert
pq\rVert}{\sin(\frac{\pi}{2}-\alpha-\beta)}=\frac{\cos(\beta)}{\cos(\theta)}\cdot\lVert
pq\rVert.$

Similarly, by the law of sines, we have

$\displaystyle\frac{\lVert
qq^{\prime}\rVert}{\sin(\measuredangle{qpq^{\prime}})}=\frac{\lVert
pq\rVert}{\sin(\measuredangle{pq^{\prime}q})}\implies\lVert
qq^{\prime}\rVert=\sin(\measuredangle{qpq^{\prime}})\cdot\frac{\lVert
pq\rVert}{\sin(\measuredangle{pq^{\prime}q})}.$

Filling in our angles, we get

$\displaystyle\lVert qq^{\prime}\rVert=\frac{\sin(\alpha)\lVert
pq\rVert}{\sin(\frac{\pi}{2}-\alpha-\beta)}=\frac{\sin(\alpha)}{\cos(\theta)}\cdot\lVert
pq\rVert.$

The proof is complete.

Let $pq$ realise $\textbf{d}(A,B)$. We consider the scenario when $\lVert
pq\rVert$ is relatively small compared to the horizontal span of (say) $B$.
Using the above lemma, we will show that we have constructed a set of edges in
$\mathcal{E}$ connecting two sample points $a\in A$ and $b\in B$, such that
the total weight of these edges approximates $\lVert pq\rVert$.

######  Lemma 2.4.

Let $pq\subseteq P^{*}$, and let $pq$ realise $\textbf{d}(A,B)$, where $p\in
A$ and $q\in B$. Let $p\in\partial A(a,a^{\prime})$, and $q\in\partial
B(b^{\prime},b)$, where points $a$ and $a^{\prime}$ (resp. $b$ and
$b^{\prime}$) are adjacent sample points on 0-region $A$ (resp. $B$). If
$\max\\{\lVert pa^{\prime}\rVert,\lVert
qb\rVert\\}\geq\mathchoice{\frac{\sin(\alpha)}{\cos(\theta)}}{(\sin(\alpha)/\cos(\theta))}{(\sin(\alpha)/\cos(\theta))}{(\sin(\alpha)/\cos(\theta))}\cdot\lVert
pq\rVert$ or $\max\\{\lVert pa\rVert,\lVert
qb^{\prime}\rVert\\}\geq(\sin(\beta)/\cos(\theta))\cdot\lVert pq\rVert$, then
there exists a path $P\subseteq\mathcal{E}$ from $A$ to $B$ such that
$\textbf{w}(P)\leq\mathchoice{\frac{\cos(\beta)}{\cos(\theta)}}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}\cdot\lVert
pq\rVert$.

######  Proof 2.5.

Without loss of generality, assume that $\lVert
qb\rVert\geq\mathchoice{\frac{\sin(\alpha)}{\cos(\theta)}}{(\sin(\alpha)/\cos(\theta))}{(\sin(\alpha)/\cos(\theta))}{(\sin(\alpha)/\cos(\theta))}\cdot\lVert
pq\rVert$. Lemma 2.2 implies that there exists a point $q^{\prime}\in\partial
B(b,q)$ such that $pq^{\prime}$ is in some direction $r(k)$, and $\lVert
pq^{\prime}\rVert\leq\mathchoice{\frac{\cos(\beta)}{\cos(\theta)}}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}\cdot\lVert
pq\rVert$.

Figure 3: In the left figure, if $pq^{\prime}$ does not overlap a 0-region, we
slide $pq^{\prime}$ until it touches a sample point. In the right figure, we
slide each inter-region segment ($cd$ as an example) the same way.

Observe that $pq$ cannot overlap any 0-region; otherwise, $P^{*}$ is not
optimal. If $pq^{\prime}$ does not overlap any 0-region (see Figure 3, left),
we fix the orientation of $pq^{\prime}$, and move $p$ along $\partial A(p,a)$
and $q$ along $\partial B(b,q)$, until $pq^{\prime}$ touches a sample point.

If $pq^{\prime}$ touches $a$ (resp. $b$), then $r(a,k)$ (resp.
$r(b,k\theta+\pi)$) hits $B$ (resp. $A$). If $pq^{\prime}$ touches a sample
point $v\notin A\cup B$, $v$ must be extreme in the direction
$r(k\theta-\pi/2)$. As a result, $r(v,k)$ hits $B$, and $r(v,k\theta+\pi)$
hits $A$. In either case, $A$ and $B$ are adjacent in some face of
$\mathcal{M}(k)$, and the edge $e=(ak(A),ak(B))$ is in $\mathcal{E}$ by
construction. As a result, $\textbf{w}(e)=\textbf{d}(A,B)=\lVert pq\rVert$.
This is also trivially true when $p$ or $q^{\prime}$ is already a sample
point.

Otherwise, the segment $pq^{\prime}$ overlaps a set $E^{\prime}$ of 0-regions,
and there exists a path $P$ from $A$ to $B$ through $E^{\prime}$ (see Figure
3, right). Since the 0-regions do not overlap, the boundaries of the 0-regions
in $E^{\prime}$ partition $pq^{\prime}$ into a set of intra-region and inter-
region segments. Let $cd$ be one among the set $S$ of inter-region segments,
where $c$ is on a 0-region $C$, and $d$ is on a 0-region $D$. Using the same
argument as above, one can slide $cd$ until it touches a sample point, and
edge $(ak(C),ak(D))\in\mathcal{E}$ exists by construction.

In total, traveling from $A$ to $B$ via the 0-regions $E^{\prime}$ must be
less costly than $\lVert pq^{\prime}\rVert$, since
$\textbf{w}(ak(C),ak(D))=\textbf{d}(C,D)\leq\lVert cd\rVert$, and the intra-
region segments have weight 0. Summing up the cost of $P$, we have that

$\displaystyle\textbf{w}(P)=\sum\limits_{cd\in
S}\textbf{w}(ak(C),ak(D))<\sum\limits_{cd\in S}\lVert cd\rVert<\lVert
pq^{\prime}\rVert=\mathchoice{\frac{\cos(\beta)}{\cos(\theta)}}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}\cdot\lVert
pq\rVert.$

###  2.3 $\Theta$-Graph

In Step 4 of Algorithm 1, we constructed a $\Theta$-graph
$\mathcal{G}_{\Theta}=(\mathcal{V}_{\Theta},\mathcal{E}_{\Theta})$ using the
defined sample points. The vertices $\mathcal{V}_{\Theta}$ are simply all
sample points. The edges in $\mathcal{E}_{\Theta}$ are constructed using the
standard $\Theta$-graph construction [11]. Recall that in Algorithm 1, for
every edge $(p,q)\in\mathcal{E}_{\Theta}$, with $p\in A$, $q\in B$, and $A\neq
B$, we add an edge $(p,q)$ to $\mathcal{E}$, and set $\textbf{w}(p,q)=\lVert
pq\rVert$.

The $\Theta$-graph constructs a set of “good” edges in $\mathcal{E}$ when the
distances between $p$ (resp. $q$) and its adjacent sample points are small
compared to $\lVert pq\rVert$. In this case, we argue that there exists a pair
of sample points $a\in A$ and $b\in B$, such that $\lVert
ab\rVert\leq\mathchoice{\frac{1}{\cos(\theta)}}{(1/\cos(\theta))}{(1/\cos(\theta))}{(1/\cos(\theta))}\cdot\lVert
pq\rVert$. Similar to Lemma 2.2, we first prove a geometric property.

######  Lemma 2.6.

Given a segment $pq$, let $\alpha$ (resp. $\beta$) be the acute angle between
$pq$ and $r(p,k+1)$ (resp. $r(p,k)$), where $\alpha+\beta=\theta<\pi/6$. Let
$q^{\prime}$ be the intersection of $r(p,k+1)$ and $r(q,k\theta+\pi/2)$, and
let $p^{\prime}$ be the intersection of $r(q,k\theta+\pi)$ and
$r(p,(k+1)\theta+\pi/2)$. Let $c$ be the intersection of $pq^{\prime}$ and
$qp^{\prime}$. We have that $\lVert cp^{\prime}\rVert+\lVert
cq^{\prime}\rVert=(\sin(\alpha)+\sin(\beta))/(\cos(\theta)\sin(\theta))$, and
$\lVert
p^{\prime}q^{\prime}\rVert=\mathchoice{\frac{1}{\cos(\theta)}}{(1/\cos(\theta))}{(1/\cos(\theta))}{(1/\cos(\theta))}\cdot\lVert
pq\rVert$.

######  Proof 2.7.

Figure 4: The construction in Lemma 2.6.

See Figure 4 for the construction. Without loss of generality, assuming
$\lVert pq\rVert=1$. Using the law of sines in the triangle $\triangle{pqc}$,
we have the following.

$\displaystyle\frac{\lVert cq\rVert}{\sin(\measuredangle{qpc})}=\frac{\lVert
pq\rVert}{\sin(\measuredangle{qcp})}\implies\lVert
cq\rVert=\frac{\sin(\measuredangle{qpc})}{\sin(\measuredangle{qcp})}\cdot\lVert
pq\rVert=\frac{\sin(\alpha)}{\sin(\pi-\theta)}=\frac{\sin(\alpha)}{\sin(\theta)}$
(1)

Observe that $\measuredangle{cqq^{\prime}}=\pi/2$, since
$\measuredangle{cqq^{\prime}}$ is the result of rotating $r(q,k\theta+\pi/2)$
counter-clockwise by $\pi/2$. Therefore, $\triangle{cqq^{\prime}}$ is a right
triangle, and we have the following.

$\displaystyle\lVert cq^{\prime}\rVert$ $\displaystyle=\frac{\lVert
cq\rVert}{\sin(\measuredangle{cq^{\prime}q})}$ $\displaystyle=\frac{\lVert
cq\rVert}{\sin(\frac{\pi}{2}-\theta)}$
$\displaystyle\triangleright\text{$\measuredangle{cq^{\prime}q}=\frac{\pi}{2}-\theta$
by construction}$
$\displaystyle=\frac{1}{\cos(\theta)}\cdot\frac{\sin(\alpha)}{\sin(\theta)}$
$\displaystyle\triangleright\text{Using (1)}$

Using an analogous computation, we obtain

$\displaystyle\lVert
cp^{\prime}\rVert=\frac{1}{\cos(\theta)}\cdot\frac{\sin(\beta)}{\sin(\theta)}.$

Combining $\lVert cp^{\prime}\rVert$ and $\lVert cq^{\prime}\rVert$, we have
that

$\displaystyle\lVert cp^{\prime}\rVert+\lVert
cq^{\prime}\rVert=\frac{\sin(\alpha)+\sin(\beta)}{\cos(\theta)\sin(\theta)}.$
(2)

Next, since $\triangle{p^{\prime}qq^{\prime}}$ is a right triangle, we can
bound $\lVert p^{\prime}q^{\prime}\rVert$ as follows.

$\displaystyle\lVert p^{\prime}q^{\prime}\rVert^{2}$ $\displaystyle=\lVert
qq^{\prime}\rVert^{2}+\lVert qp^{\prime}\rVert^{2}$
$\displaystyle=(\mathchoice{\frac{\sin(\alpha)}{\cos(\theta)}}{(\sin(\alpha)/\cos(\theta))}{(\sin(\alpha)/\cos(\theta))}{(\sin(\alpha)/\cos(\theta))})^{2}+(\lVert
cp^{\prime}\rVert+\lVert cq\rVert)^{2}$
$\displaystyle\triangleright\text{Using Lemma\leavevmode\nobreak\
\ref{lem:cost_of_rotation}}$
$\displaystyle=(\mathchoice{\frac{\sin(\alpha)}{\cos(\theta)}}{(\sin(\alpha)/\cos(\theta))}{(\sin(\alpha)/\cos(\theta))}{(\sin(\alpha)/\cos(\theta))})^{2}+(\frac{\sin(\beta)}{\cos(\theta)\sin(\theta)}+\frac{\sin(\alpha)}{\sin(\theta)})^{2}$
$\displaystyle\triangleright\text{Using (2)}$
$\displaystyle=(\mathchoice{\frac{\sin(\alpha)}{\cos(\theta)}}{(\sin(\alpha)/\cos(\theta))}{(\sin(\alpha)/\cos(\theta))}{(\sin(\alpha)/\cos(\theta))})^{2}+(\frac{\sin(\theta-\alpha)}{\cos(\theta)\sin(\theta)}+\frac{\sin(\alpha)}{\sin(\theta)})^{2}$
$\displaystyle=(\mathchoice{\frac{\sin(\alpha)}{\cos(\theta)}}{(\sin(\alpha)/\cos(\theta))}{(\sin(\alpha)/\cos(\theta))}{(\sin(\alpha)/\cos(\theta))})^{2}+(\frac{\sin(\theta)\cos(\alpha)-\sin(\alpha)\cos(\theta)}{\cos(\theta)\sin(\theta)}+\frac{\sin(\alpha)}{\sin(\theta)})^{2}$
$\displaystyle=(\mathchoice{\frac{\sin(\alpha)}{\cos(\theta)}}{(\sin(\alpha)/\cos(\theta))}{(\sin(\alpha)/\cos(\theta))}{(\sin(\alpha)/\cos(\theta))})^{2}+(\frac{\cos(\alpha)}{\cos(\theta)}-\frac{\sin(\alpha)}{\sin(\theta)}+\frac{\sin(\alpha)}{\sin(\theta)})^{2}$
$\displaystyle=(\mathchoice{\frac{1}{\cos(\theta)}}{(1/\cos(\theta))}{(1/\cos(\theta))}{(1/\cos(\theta))})^{2}$

Since $0<\theta<\pi/6$, all terms are greater than 0, and $\lVert
p^{\prime}q^{\prime}\rVert=\mathchoice{\frac{1}{\cos(\theta)}}{(1/\cos(\theta))}{(1/\cos(\theta))}{(1/\cos(\theta))}\cdot\lVert
pq\rVert$.

In the case that both $p$ and $q$ are close to their adjacent sample points,
we argue that there exists a pair $(a,b)$ of sample points such that $\lVert
ab\rVert$ approximates $\lVert pq\rVert$.

######  Lemma 2.8.

Let $pq\subseteq P^{*}$, and let $pq$ realise $\textbf{d}(A,B)$, where $p\in
A$ and $q\in B$. Let $p\in\partial A(a^{\prime},a)$, and $q\in\partial
B(b,b^{\prime})$, where points $a$ and $a^{\prime}$ (resp. $b$ and
$b^{\prime}$) are adjacent sample points on $A$ (resp. $B$). If $\max\\{\lVert
pa^{\prime}\rVert,\lVert
qb\rVert\\}<\mathchoice{\frac{\sin(\alpha)}{\cos(\theta)}}{(\sin(\alpha)/\cos(\theta))}{(\sin(\alpha)/\cos(\theta))}{(\sin(\alpha)/\cos(\theta))}\cdot\lVert
pq\rVert$ and $\max\\{\lVert pa\rVert,\lVert
qb^{\prime}\rVert\\}<(\sin(\beta)/\cos(\theta))\cdot\lVert pq\rVert$, then
$\textbf{d}(a,b)<\mathchoice{\frac{1}{\cos(\theta)}}{(1/\cos(\theta))}{(1/\cos(\theta))}{(1/\cos(\theta))}\cdot\lVert
pq\rVert$.

######  Proof 2.9.

Figure 5: With $b$ fixed, moving $a$ to $p^{\prime}$ strictly increases
$\lVert ab\rVert$.

We argue that $\lVert ab\rVert<\lVert p^{\prime}q^{\prime}\rVert$ (see Figure
5), where $q^{\prime}$ (resp. $p^{\prime}$) is the intersection of
$r(p,(k+1)\theta)$ (resp. $r(q,k\theta+\pi)$) and $B$ (resp. $A$). Let
$p^{\prime\prime}$ (resp. $q^{\prime\prime}$) be the intersection of
$r(q,k\theta+\pi)$ (resp. $r(p,k+1)$) and $l_{t}(p)$ (resp. $l_{t}(q)$).
Without loss of generality, assume $pq$ is parallel to the $y$-axis, and
$y(q)>y(p)$, and consider the sample point $a$ next to $p$ counter-clockwise.

We will first show that $a$ must reside in a circular sector. The region $A$
is convex; therefore $a$ must be below the supporting line $l_{t}(p)$. Due to
how the sample points are constructed, the sample point $a$ must be above
$r(p,(k+1)\theta+\pi/2)$. Since $\lVert
pa\rVert<(\sin(\beta)/\cos(\theta))\cdot\lVert pq\rVert$, $a$ must reside in
the disk $D=D(p,\lVert pp^{\prime}\rVert)$ centered at $p$ with radius $\lVert
pp^{\prime}\rVert$. Combining the above restrictions, we have that $a$ must
reside in the smaller circular sector $S$ of $D$ enclosed by $l_{t}(p)$ and
$pp^{\prime}$. An analogous argument shows that $b$ must reside in the smaller
circular sector of $D(q,\lVert qq^{\prime}\rVert)$ enclosed by $l_{t}(q)$ and
$qq^{\prime}$.

Consider the line $l$ through $ab$, and observe that pushing $a$ along $l$
towards the boundary of $S$ strictly increases $\lVert ab\rVert$. Next, now
that $a$ lies on the boundary of $S$, we push $a$ towards $p^{\prime}$ along
the boundary of $S$. This also increases $\lVert ab\rVert$, since
$\measuredangle{bap^{\prime}}\geq\pi/2$. Now that $a=p^{\prime}$, an analogous
argument applies to $b$, since
$\measuredangle{p^{\prime}bq^{\prime}}\geq\pi/2$. In conclusion, $\lVert
ab\rVert\leq\lVert p^{\prime}q^{\prime}\rVert$.

By Lemma 2.6, $\lVert ab\rVert\leq\lVert
p^{\prime}q^{\prime}\rVert\leq\mathchoice{\frac{1}{\cos(\theta)}}{(1/\cos(\theta))}{(1/\cos(\theta))}{(1/\cos(\theta))}\cdot\lVert
pq\rVert$, and the proof is complete.

###  2.4 The quality of the path

For now, assume that $s$ and $t$ lie in some 0-region. An optimal $s$-$t$ path
$P^{*}$ consists of a set of segments, where the endpoints of each segment lie
on the boundaries of the 0-regions. A segment $pq$ either lies within a
0-region or connects two different 0-region. Since it costs nothing to follow
an edge inside a 0-region, the weight of $P$ is the total weight of those
edges connecting different 0-regions.

Let $pq$ realise the distance between 0-regions $A$ and $B$, where $p$ lies on
$\partial A$ between sample points $a$ and $a^{\prime}$, and $q$ lies on
$\partial B$ between sample points $b$ and $b^{\prime}$. In Lemma 2.4, we have
shown that if $\max\\{\lVert pa^{\prime}\rVert,\lVert
qb\rVert\\}\geq\mathchoice{\frac{\sin(\alpha)}{\cos(\theta)}}{(\sin(\alpha)/\cos(\theta))}{(\sin(\alpha)/\cos(\theta))}{(\sin(\alpha)/\cos(\theta))}\cdot\lVert
pq\rVert$ or $\max\\{\lVert pa\rVert,\lVert
qb^{\prime}\rVert\\}\geq(\sin(\beta)/\cos(\theta))\cdot\lVert pq\rVert$, there
exists a path $P\subseteq\mathcal{E}$ from a sample point on $A$ to a sample
point on $B$ of length at most
$\mathchoice{\frac{\cos(\beta)}{\cos(\theta)}}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}\cdot\lVert
pq\rVert$.

In Lemma 2.8, we have shown that if $\max\\{\lVert pa^{\prime}\rVert,\lVert
qb\rVert\\}<\mathchoice{\frac{\sin(\alpha)}{\cos(\theta)}}{(\sin(\alpha)/\cos(\theta))}{(\sin(\alpha)/\cos(\theta))}{(\sin(\alpha)/\cos(\theta))}\cdot\lVert
pq\rVert$ and $\max\\{\lVert pa\rVert,\lVert
qb^{\prime}\rVert\\}<(\sin(\beta)/\cos(\theta))\cdot\lVert pq\rVert$, there
exist sample points $a\in A$ and $b\in B$, such that
$\textbf{d}(a,b)<\mathchoice{\frac{1}{\cos(\theta)}}{(1/\cos(\theta))}{(1/\cos(\theta))}{(1/\cos(\theta))}\cdot\lVert
pq\rVert$. To obtain a path between $a$ and $b$ in this case, we rely on the
$\Theta$-graph. The tightest bounds on the length of this path are due to Bose
et al. [4], who showed that the spanning ratio of a $\Theta$-graph is at most
$r_{\theta}=1+2\sin(\theta/2)/(\cos(\theta/2)-\sin(\theta/2))$.

In summary, if $pq\subseteq P^{*}$, there exists a path $P$ from $A$ to $B$
such that

$\displaystyle\textbf{w}(P)\leq\max\\{\mathchoice{\frac{\cos(\beta)}{\cos(\theta)}}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))},\mathchoice{\frac{1}{\cos(\theta)}}{(1/\cos(\theta))}{(1/\cos(\theta))}{(1/\cos(\theta))}\cdot
r_{\theta}\\}\cdot\textbf{w}(P^{*})\leq\mathchoice{\frac{1}{\cos(\theta)}}{(1/\cos(\theta))}{(1/\cos(\theta))}{(1/\cos(\theta))}\cdot
r_{\theta}\cdot\textbf{w}(P^{*}).$

Given an approximation factor $0<\varepsilon<1$, we compute a proper value for
$0<\theta<\pi/6$ as follows.

$\displaystyle\mathchoice{\frac{1}{\cos(\theta)}}{(1/\cos(\theta))}{(1/\cos(\theta))}{(1/\cos(\theta))}\cdot(1+\frac{2\sin(\frac{\theta}{2})}{\cos(\frac{\theta}{2})-\sin(\frac{\theta}{2})})=\frac{1}{1-\sin(\theta)}\leq
1+\varepsilon\implies\theta\leq\sin^{-1}(\frac{\varepsilon}{1+\varepsilon})\in
O(\varepsilon)$

Using $\theta$, we can construct the data structure $\mathcal{B}$. Combining
Lemma 2.4 and Lemma 2.8, we have the following.

######  Lemma 2.10.

Data structure $\mathcal{B}$ contains a path $P\subseteq\mathcal{E}$ from
sample point $a$ to sample point $b$ such that
$\textbf{w}(P)\leq(1+\varepsilon)\cdot\textbf{w}(P^{*})$, where $P^{*}$ is the
optimal path from $a$ to $b$.

###  2.5 Finding a shortest path amidst $0$-regions

Now that we know good paths exist between all pairs of sample points, it
remains to include our arbitrary query points $s$ and $t$. Given the data
structure $\mathcal{B}=\\{\mathcal{M}(k)\mid\forall
k\in[0,2\pi/\theta),k\in\mathbb{Z}\\}\cup\\{\mathcal{G},\mathcal{G}_{\Theta}\\}$,
a point $s$, and a point $t$, we query the approximate shortest path from $s$
to $t$ using Algorithm 2.

Algorithm 2 Query $s$-$t$ weighted shortest path amidst 0-regions

This algorithm takes as input a point $s$ and a point $t$, and a data
structure $\mathcal{B}=\\{\mathcal{M}(k)\mid\forall
k\in[0,2\pi/\theta),k\in\mathbb{Z}\\}\cup\\{\mathcal{G},\mathcal{G}_{\Theta}\\}$
storing a set of 0-regions. It outputs an $(1+\varepsilon)$-approximated
weighted shortest path from $s$ to $t$. In Step 1 and Step 2, this algorithm
shows how to add $s$ to $\mathcal{B}$, and the same operations are used to add
$t$.

  1. 1.

For each trapezoidal map $\mathcal{M}(k)$, do the following for point $s$.

    1. (a)

Query the face $F$ containing $s$.

    2. (b)

Let $F$ be adjacent to 0-regions $A$ and $B$. Add $e=(s,ak(A))$ to
$\mathcal{E}$, and set $\textbf{w}(e)=\textbf{d}(s,A)$. Perform the same
operation for $s$ and $B$.

  2. 2.

Add $s$ to $\mathcal{G}_{\Theta}$. Specifically, using $s$ as the apex, we
construct a set of disjoint cones with $\theta$-angle. For each point $p$
closest to $s$ in each cone, add $e=(s,p)$ to $\mathcal{E}$, and set
$\textbf{w}(e)=\lVert sp\rVert$. For every existing vertex
$p\in\mathcal{G}_{\Theta}$, and every existing edge
$(p,q)\in\mathcal{E}_{\Theta}$, if $s$ is closer to $p$ than $q$ is, add
$e=(s,p)$ to $\mathcal{E}$, and set $\textbf{w}(e)=\lVert sp\rVert$. (Note
that $\Theta$-graph uses projected distance instead of Euclidean distance.)

  3. 3.

Use Dijkstra’s shortest path algorithm to compute a path $P^{\prime}$ from $s$
to $t$ in $\mathcal{G}$. Transform $P^{\prime}$ into a path $P$ in the
original environment and return $P$.

Once $s$ and $t$ are added to $\mathcal{B}$, they are treated as 0-region with
no interior. The point $s$ is its extreme point in every direction. Therefore,
the distance between $s$ and its adjacent sample points is $0$. As a result,
Lemma 2.4 and Lemma 2.8 both apply. Thus $\mathcal{B}$ with $s$ and $t$ added
contains a $(1+\varepsilon)$-approximation of the shortest path from $s$ to
$t$, which Dijkstra’s shortest path algorithm will find.

####  2.5.1 Analysis

Finally, we look at the query time. Recall that $\varepsilon\in O(\theta)$. In
Step 1, we consider $O(1/\varepsilon)$ trapezoidal maps. For each trapezoidal
map, it takes $O(\log(n/\varepsilon))$ time to perform a point-location query
[11], and it takes $O(\log N)$ time to compute $\textbf{d}(s,A)$ [15]. In Step
2, it takes $O(n/\varepsilon^{2}+(n/\varepsilon)\log(n/\varepsilon))$ time to
find the closest point of $s$ in each cone, and at the same time check if $s$
is closest to any point $p$. In Step 3, it takes
$O(|\mathcal{E}|+|\mathcal{V}|\log|\mathcal{V}|)=O(n/\varepsilon^{2})$ time to
run Dijkstra’s shortest path algorithm to find the shortest path $P^{\prime}$
from $s$ to $t$ in $\mathcal{V}$ [16]. It takes $O(n/\varepsilon^{2}+N)$ time
to transform $P^{\prime}$ into a path $P$ in the environment. The query time
is $O(N+n/\varepsilon^{2}+(n/\varepsilon)\log(n/\varepsilon)+(\log
N)/\varepsilon)$.

See 1.1

##  3 Partial weak Fréchet similarity

This section highlights one application of our data structure: approximating
the partial weak Fréchet similarity. This problem was previously considered by
Buchin et al. [7] and De Carufel et al. [13]. We start with an introduction
for the Fréchet distance and the weak Fréchet distance, eventually leading us
to the formal definition of the partial weak Fréchet similarity problem.

The Fréchet distance is a popular measure of the similarity between two
polygonal curves. An _orientation-preserving reparameterisation_ is a
continuous and bijective function $f:[0,1]\rightarrow[0,1]$ such that
$f(0)=0$, and $f(1)=1$. The $0pt_{f,g}(\pi,\sigma)$ between two curves $\pi$
and $\sigma$ with respect to the reparameterisations $f$ and $g$, is defined
as follows.

$\displaystyle
0pt_{f,g}(\pi,\sigma)=\max_{t\in[0,1]}\lVert\pi(f(t))-\sigma(g(t))\rVert$

Consider the scenario where a person is walking his dog with a leash
connecting them: the person needs to stay on $\pi$ while walking according to
$f$, and the dog needs to stay on $\sigma$ while walking according to $g$. The
maximum leash length is the width between $\pi$ and $\sigma$ with respect to
the reparameterisations $f$ and $g$. The standard Fréchet distance
$\delta_{F}(\pi,\sigma)$ is the minimum leash length required over all
possible walks (defined by reparameterisations $f$ and $g$).

$\displaystyle\delta_{F}(\pi,\sigma)=\inf_{f,g\in[0,1]\rightarrow[0,1]}0pt_{f,g}(\pi,\sigma)$

Problems relating to the Fréchet distance are commonly solved in a
configuration space called the _freespace diagram_. The _free space_
$\mathcal{F}_{d}(\pi,\sigma)$ with respect to the Fréchet distance $d$ is the
union of all pairs of points $x\in\pi$ and $y\in\sigma$ such that the distance
between $x$ and $y$ is at most $d$. As opposed to the free space, we will call
$[0,\lVert\pi\rVert]\times[0,\lVert\sigma\rVert]\setminus\mathcal{F}_{d}(\pi,\sigma)$
the _forbidden space_.

$\displaystyle\mathcal{F}_{d}(\pi,\sigma)=\\{(x,y)\in[0,\lVert\pi\rVert]\times[0,\lVert\sigma\rVert]\mid\lVert\pi(x)-\sigma(y)\rVert\leq
d\\}$

The _freespace diagram_ $\mathcal{D}_{d}(\pi,\sigma)$ is a data structure that
stores the free space $\mathcal{F}_{d}(\pi,\sigma)$ in $n^{2}$ cells. Alt and
Godau [3] showed that the intersection of the free space with each cell is the
intersection of an ellipse and a rectangle. Therefore the free space in each
cell is convex, and its boundary is of constant complexity. For two polygonal
curves with complexity $n$, Alt and Godau [3] proved the following fact.

######  Fact 1.

The freespace diagram contains at most $n^{2}$ cells, and it can be
constructed in $O(n^{2}\log n)$ time. The free space inside each cell is the
intersection of an ellipse and a rectangle.

It is well-known that if one can find an $xy$-monotone path in
$\mathcal{D}_{d}(\pi,\sigma)$ from the bottom-left corner $s$ to the top-right
corner $t$ via the free space, then $\delta_{F}(\pi,\sigma)\leq d$.

The notion of weak Fréchet distance relaxes the requirement of the
reparameterisation $f$: it still needs to be continuous but not bijective.
This means that the person and the dog can walk backward. To determine if the
weak Fréchet distance $\delta_{wF}(\pi,\sigma)$ is at most $d$, we need to
find only a (potentially not $xy$-monotone) path through the free space from
$s$ to $t$ in $\mathcal{D}_{d}(\pi,\sigma)$. Buchin et al. [8] showed that
there is no strongly subquadratic time algorithm for approximating the weak
Fréchet distance within a factor less than 3 unless the strong exponential-
time hypothesis fails.

Buchin et al. [7] proposed the _partial Fréchet similarity_ (partial
similarity in short) to deal with the Fréchet distance’s sensitivity to
outliers. Instead of determining whether a leash of length $d$ is enough to
complete the walk, partial similarity determines how much can be completed
given a leash of length $d$. The partial similarity is the total length of the
portion of two curves that are matched under the Fréchet distance $d$.

Let $\textbf{d}_{p}(x,y)$ be the distance between point $x$ and point $y$
under the $L_{p}$ norm. Let $\lVert v\rVert$ be the $L_{2}$ norm of the vector
$v$. Under the $L_{p}$ metric, given the desired Fréchet distance $d$, the
partial similarity $S_{f,g}(\pi,\sigma)$ of curves $\pi$ and $\sigma$ with
respect to the reparameterisations $f$ and $g$ is formally defined as follows
[7].

$\displaystyle
S_{f,g}(\pi,\sigma)=\int_{\textbf{d}_{p}(\pi(f(t)),\sigma(g(t))\leq
d}(\lVert\pi(f(t))^{\prime}\rVert+\lVert\sigma(g(t))^{\prime}\rVert)dt$

Naturally, we want to compute a pair of reparameterisations $f$ and $g$ that
maximise the partial similarity. To do this, Buchin et al. [7] proposed a
cubic time algorithm. They showed that it is sufficient to find an
$xy$-monotone path $P$ from $s$ to $t$ such that $P$ intersects as much free
space as possible, i.e., $\lVert P\cap\mathcal{F}_{Q}(d,P)\rVert_{p}$ should
be maximised. When the distance measure between two curves is the more natural
$L_{2}$-metric, De Carufel et al. [13] proposed a cubic time algorithm with an
additive error. They showed that finding a path that intersects as much free
space as possible is equivalent to finding a path that intersects as little
forbidden space as possible. They formalised the latter as the Minimum-
Exclusion (MinEx) problem. They also showed that the MinEx problem is
equivalent to the weighted shortest $xy$-monotone path problem: computing a
$xy$-monotone weighted shortest path $P$ from $s$ to $t$ in the freespace
diagram, where the weight in the forbidden space is one, and the weight in the
free space is zero. Under the weak Fréchet distance, the monotonicity
requirement is removed.

Therefore, solving the weak Fréchet version of the MinEx problem under the
$L_{2}$ metric is equivalent to finding a weighted shortest path amidst a set
of $O(n^{2})$ non-overlapping and convex $0$-regions, where each 0-region is
of constant complexity. Using Theorem 1.1 and Fact 1, we have the following
theorem.

See 1.2

##  4 Shortest path amidst 0-regions and obstacles

In this section, we generalise our data structure from Section 2 to allow
convex obstacles that cannot be traversed, i.e., obstacles with weight
$\infty$. Our problem is finding an approximate shortest path amidst 0-regions
and obstacles. More concretely, we consider the following problem.

######  Problem 4.1.

In the planar-subdivision induced by the plane with weight $1$, and a set of
non-overlapping convex regions consisting of obstacles with weight $\infty$,
and $0$-regions with weight $0$, given an approximation error
$0<\varepsilon<1$, find a $(1+\varepsilon)$-approximate weighted shortest path
from point $s$ to point $t$.

In this section, we redefine $\textbf{d}(A,B)$ as the minimum distance between
two geometric regions $A$ and $B$ in a $0/1/\infty$ weighted setting. The
$\Theta$-graph can be constructed in an environment with obstacles. Clarkson
[10] described such construction over points and polygonal obstacles, and
proved that a path that $(1+\varepsilon)$-approximates $\textbf{d}(a,b)$
exists in the $\Theta$-graph, where $a$ and $b$ are vertices. We will use this
$\Theta$-graph in the rest of the paper.

Like in the previous section, we will first describe the construction of the
data structure $\mathcal{B}$ and analyse the time and space complexity. We
then show that $\mathcal{G}\in\mathcal{B}$ contains a good path between every
pair of sample points. We use this to argue the approximation ratio for
arbitrary $s$ and $t$.

###  4.1 Construction of the data structure

In order to deal with obstacles, we need to define two new types of sample
points. For clarity, we refer to the sample points defined previously as the
original sample points. In Section 2, a trapezoidal map $\mathcal{M}(k)$ was
only used to determine if two 0-regions should be connected, and we did not
explicitly compute the intersection of a vertical segment and the boundary of
a region. With the introduction of obstacles, we do need such intersections.
Consider a sample point $a$. When constructing $\mathcal{M}(k)$, we shoot two
vertical rays from $a\in A$, one upwards and one downwards. Let $p$ be the
first intersection of $r(a,k)$ with the boundary of some region that is not
$A$. We call $p$ a propagated sample point.

The other type of sample points we need is the tangent sample points. Given
two disjoint obstacles $A$ and $B$, and a common tangent $l$, if $l$ touches
$A$ at point $a$ and $B$ at $b$, we add $a$ and $b$ as tangent sample points.
When we say a point $a$ is a sample point, $a$ can be any type of sample
point.

Recall that $\mathtt{simpl}(A)$ is the simplified region by connecting every
pair of adjacent sample points of $A$. $\mathtt{simpl}(\mathcal{Z})$ is the
set of simplified 0-regions, and $\mathtt{simpl}(\mathcal{O})$ is the set of
simplified obstacles. We formally define the construction of our data
structure. Given a set $\mathcal{O}$ of convex obstacles and a set
$\mathcal{Z}$ of convex $0$-regions, we build our data structure using
Algorithm 3.

Algorithm 3 Construct $\mathcal{B}$ with 0-regions and obstacles

This algorithm takes as input a set of non-overlapping and convex regions,
including 0-regions $\mathcal{Z}$ and obstacles $\mathcal{O}$, and constructs
a data structure $\mathcal{B}$. The undirected graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$ is initially empty.

  1. 1)

Compute the original sample points
$\mathcal{SP}(\mathcal{Z})\cup\mathcal{SP}(\mathcal{O})$, and add them to
$\mathcal{V}$.

  2. 2)

For each direction $r(k)$, generate a trapezoidal map $\mathcal{M}(k)$ using
$\mathtt{simpl}(\mathcal{Z})\cup\mathtt{simpl}(\mathcal{O})$.

  3. 3)

For every $\mathcal{M}(k)$, do the following for every face $F$ adjacent to
$A$ and $B$, $A\neq B$.

    1. (a)

Compute the propagated sample points, and add them to $\mathcal{V}$.

    2. (b)

If $A$ and $B$ are both 0-regions, add $e=(ak(A),ak(B))$ to $\mathcal{E}$, and
set $\textbf{w}(e)=\textbf{d}(A,B)$.

    3. (c)

If at least one of $A$ and $B$ is an obstacle, let $ab$ and
$a^{\prime}b^{\prime}$ be the vertical segments defining $F$, where
$a,a^{\prime}\in A$, and $b,b^{\prime}\in B$. Add edges $e_{1}=(a,b)$ and
$e_{2}=(a^{\prime},b^{\prime})$ to $\mathcal{E}$. Set
$\textbf{w}(e_{1})=\lVert ab\rVert$ and $\textbf{w}(e_{2})=\lVert
a^{\prime}b^{\prime}\rVert$.

    4. (d)

If $A$ and $B$ are both obstacles, we compute their common tangents. For each
common tangent that touches $A$ at $a$ and $B$ at $b$, add $a$ and $b$ to
$\mathcal{V}$.

  4. 4)

Redefine $\mathtt{simpl}(A)$ as the polygon generated by connecting adjacent
sample points of $A$, original, propagated, and tangent sample points
included. With $\mathcal{V}$ and $\mathtt{simpl}(\mathcal{O})$ as the input,
generate a $\Theta$-graph
$\mathcal{G}_{\Theta}=(\mathcal{V},\mathcal{E}_{\Theta})$.

     * •

For each edge $(p,q)\in\mathcal{E}_{\Theta}$, if $p$ and $q$ belongs to
different regions $A$ and $B$, add $e=(p,q)$ to $\mathcal{E}$ and set
$\textbf{w}(e)=\lVert pq\rVert$.

  5. 5)

For every pair of adjacent sample points $a,a^{\prime}$ on an obstacle, add
$e=(a,a^{\prime})$ to edges, and set $\textbf{w}(e)=\lVert aa^{\prime}\rVert$.

  6. 6)

Pick an arbitrary sample point as the anchor $ak(A)$ for every
$A\in\mathcal{Z}$. For each sample point $a$ of a $0$-region $A$, add
$e=(a,ak(A))$ to $\mathcal{E}$, and set $\textbf{w}(e)=0$.

  7. 7)

Return $\mathcal{B}=\\{\mathcal{M}(k)\mid\forall
k\in[0,2\pi/\theta),k\in\mathbb{Z}\\}\cup\\{\mathcal{G},\mathcal{G}_{\Theta}\\}$
as the data structure.

####  4.1.1 Analysis

Recall that we are given an approximation error $\varepsilon$ and a set of
non-overlapping convex regions consisting of obstacles $\mathcal{O}$ and
0-regions $\mathcal{Z}$. There are $n$ regions, and the total complexity of
$\mathcal{O}\cup\mathcal{Z}$ is $O(N)$. In Step 1, it takes
$O(N+n/\varepsilon)$ time to compute the sample points. In Step 2, it takes
$O((n/\varepsilon^{2})\log(n/\varepsilon))$ expected time to construct the
trapezoidal maps [11].

Step 3 considers $O(n/\varepsilon^{2})$ trapezoidal map faces. In Step 3a,
given a vertical segment $c$ intersecting a non-vertical segment $ab\in A$, it
takes $O(\log N)$ time to use a binary search on $\partial A(a,b)$ to find the
intersection of $c$ and $\partial A(a,b)$. In Step 3b, using the algorithm by
Edelsbrunner [15], it takes $O(\log N)$ time to compute the distance between
two 0-regions. In Step 3c, it takes constant time to compute the length of the
vertical segments. In Step 3d, using the algorithm by Kirkpatrick and Snoeyink
[19], and Guibas et al. [18], it takes $O(\log N)$ time to compute at most
four common tangents. In total, Step 3 takes $O((n/\varepsilon^{2})\log(N))$
time, and we add at most $O(n/\varepsilon^{2})$ tangent and propagated sample
points.

In Step 4, using Clarkson’s algorithm [10], it takes
$O((n/\varepsilon^{3})\log(n/\varepsilon))$ time to generate a $\Theta$-graph
with obstacles using $O(n/\varepsilon^{2})$ sample points and
$O(1/\varepsilon)$ cones. In Step 5, it takes $O(n/\varepsilon^{2}+N)$ time to
generate an edge and set the weight for every pair of adjacent sample points.
Step 6 takes $O(n/\varepsilon^{2})$ time to connect every sample point in a
0-region to its anchor.

We generate $O(n/\varepsilon)$ original sample points. We generate a constant
number of propagated and tangent sample points for each of the
$O(n/\varepsilon^{2})$ faces. As a result, each propagated or tangent sample
point contributes a constant number of edges in $\mathcal{E}$. A
$\Theta$-graph constructed with $O(n/\varepsilon^{2})$ sample points, and
$O(1/\varepsilon)$ cones has at most $O(n/\varepsilon^{3})$ edges. Therefore
$|\mathcal{G}|=O(n/\varepsilon^{3})$. We summarise the complexities below.

######  Lemma 4.2.

Given an approximation error $0<\varepsilon<1$, and $n$ non-overlapping convex
regions including $0$-regions and obstacles with total complexity $N$, one can
build the data structure $\mathcal{B}$ in
$O(N+(n/\varepsilon^{3})(\log(n/\varepsilon)+\log N))$ expected time, and the
total size of $\mathcal{B}$ is $O(N+n/\varepsilon^{3})$.

The structure of the rest of the section is as follows. By Lemma 4.3, the
distance between two adjacent sample points on the boundary of an obstacle
approximates the straight line segment. Therefore, we show that we can “snap”
the vertices of an optimal path to our sample points. For every segment
$pq\subseteq P^{*}$, we then argue that either the trapezoidal map or the
$\Theta$-graph contains a path approximating $\lVert pq\rVert$ to within a
factor of $1+\varepsilon$.

###  4.2 Walking on the boundary is not expensive

We first argue that if $a$ and $a^{\prime}$ are adjacent sample points of $A$,
then $\lVert aa^{\prime}\rVert$ approximates $\lVert\partial
A(a,a^{\prime})\rVert$ within a factor of $\sec(\theta/2)$. Therefore, if we
find a path $P$ amidst the simplified obstacles, we only need to pay a small
factor to transform $P$ into a path amidst the original obstacles. Then, we
prove that if $pq$ is part of the optimal path, we can replace $pq$ with a
path $P\subseteq\mathcal{E}$, such that $\textbf{w}(P)$ approximates $\lVert
pq\rVert$.

######  Lemma 4.3.

Let $a$ and $b$ be adjacent sample points on $\partial A$, where $a$ appear
after $b$ in a counter-clockwise walk. We have that $\lVert\partial
A(a,b)\rVert\leq\mathchoice{\sec(\frac{\theta}{2})}{\sec(\theta/2)}{\sec(\theta/2)}{\sec(\theta/2)}\cdot\lVert
ab\rVert$.

######  Proof 4.4.

Figure 6: The length of $\partial A(a,b)$ (blue) is upperbounded by $\lVert
av\rVert+\lVert bv\rVert$ (red). The two lines are the tangent lines of $A$
through $a$ and $b$, respectively.

See Figure 6. Let $v$ be the intersection of $l_{t}(a)$ and $l_{t}(b)$. By
convexity of $A$, $\lVert\partial A(a,b)\rVert\leq\lVert av\rVert+\lVert
vb\rVert$. By the construction of the sample points,
$\measuredangle{vab}+\measuredangle{vba}\leq\theta$. Let
$\alpha=\measuredangle{vab}$, and let $\beta=\measuredangle{vba}$. Then, using
the law of sines, we have the following.

$\displaystyle\lVert\partial A(a,b)\rVert\leq\lVert av\rVert+\lVert
bv\rVert\leq\frac{\sin(\beta)\cdot\lVert
ab\rVert}{\sin(\theta)}+\frac{\sin(\alpha)\cdot\lVert
ab\rVert}{\sin(\theta)}=\frac{\sin(\alpha)+\sin(\beta)}{\sin(\theta)}\cdot\lVert
ab\rVert$

The above expression is maximised when $\alpha=\beta=\theta/2$, resulting in
the following.

$\displaystyle\lVert\partial
A(a,b)\rVert\leq\frac{2\sin(\frac{\theta}{2})}{\sin(\theta)}=\sec\left(\frac{\theta}{2}\right)\cdot\lVert
ab\rVert$

The above lemma implies the following. Let $\textbf{d}_{\textbf{S}}(a,b)$ be
the distance between point $a$ and point $b$ in the environment with
simplified obstacles and simplified 0-regions, and let $P$ be the path
achieving this distance. If we partition $P$ using the sample points, in the
worst case, each segment connects adjacent sample points on obstacles. This
implies the following corollary.

######  Corollary 4.5.

Let $a$ and $b$ be two sample points. We have that
$\textbf{d}(a,b)\leq\mathchoice{\sec(\frac{\theta}{2})}{\sec(\theta/2)}{\sec(\theta/2)}{\sec(\theta/2)}\cdot\textbf{d}_{\textbf{S}}(a,b)$.

###  4.3 Snapping a segment of the optimal path to the sample points

Gewali et al. [17] defined three types of locally optimal edges joining two
simple polygonal regions, and they proved that the shortest path from $s$ to
$t$ must be comprised of these locally optimal edges [17, Lemma 2.5] (ignoring
edges in 0-regions). For convex obstacles and 0-regions, we need to consider
only four types of segments.

######  Fact 2.

If segment $pq$ is in the optimal weighted path $P^{*}$ amidst convex and non-
overlapping 0-regions and obstacles, there must exists two supporting lines
$l_{t}(p)$ and $l_{t}(q)$ such that $pq$ belong to one of the following cases
(ignoring segments in 0-regions).

  1. 1)

$pq$ connects two 0-regions such that $pq\perp l_{t}(q)$ and $pq\perp
l_{t}(p)$.

  2. 2)

$pq$ connects the point $p$ on a 0-region $A$ and the point $q$ on an obstacle
$B$ such that $pq\subset l_{t}(q)$, and $pq\perp l_{t}(p)$.

  3. 3)

$pq$ lies on one of the common tangent of two different obstacles.

  4. 4)

$p$ and $q$ are two points on the same obstacle, and $pq=\partial A(p,q)$ or
$pq=\partial A(q,p)$.

In Section 4.3.1, 4.3.2, and 4.3.3, we handle each type of edge in Case 1, 2,
and 3, respectively. For an edge $pq$ in each of these cases, we argue that a
good path in our data structure approximates $pq$. Section 4.4 summarises the
approximating ratio using the Case 4 edges.

More specifically, in the following subsections, we argue that for each type
of segment $pq\subseteq P^{*}$, there exists a path $P$ constructed using our
data structure such that the length of $P$ approximates $\lVert pq\rVert$. If
$pq$ is parallel to a direction $r(k)$, based on the construction of the
sample points and Fact 2, $p$ and $q$ are both sample points, and the argument
is straightforward. Therefore, we will focus on the scenario where $pq$ is not
parallel to any predefined direction. We assume without loss of generality
that $pq$ lies between the direction $r(k)$ and $r(k+1)$, and $\alpha$ (resp.
$\beta$) is the measure of the acute angle between $r(p,k)$ (resp. $r(p,k+1)$)
and $pq$. Furthermore, by Corollary 4.5, we consider only simplified
obstacles.

####  4.3.1 Case 1: $pq$ connects two $0$-regions

We observe that, unfortunately, Lemma 2.4 does not trivially apply. When we
rotate $pq$ to $pq^{\prime}$, if $pq^{\prime}$ overlaps obstacles, a path
generated using the skewed set of obstacles can be much longer than $\lVert
pq^{\prime}\rVert$, since the path would have to take a detour around the
obstacles. The following lemmas resolve this issue.

######  Lemma 4.6.

Let $A$ and $B$ be two $0$-regions. Let $pq\subseteq P^{*}$, where
$p\in\partial A$, and $q\in\partial B$. If $\lVert
qb\rVert\geq\mathchoice{\frac{\sin(\alpha)}{\cos(\theta)}}{(\sin(\alpha)/\cos(\theta))}{(\sin(\alpha)/\cos(\theta))}{(\sin(\alpha)/\cos(\theta))}\cdot\lVert
pq\rVert$, where $b$ is a sample point adjacent to $q$, then there exists a
sample point $a\in\partial A$ such that
$\textbf{d}_{\textbf{S}}(a,b)\leq\mathchoice{\frac{\cos(\beta)}{\cos(\theta)}}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}\cdot\lVert
pq\rVert$.

######  Proof 4.7.

Figure 7: The $x$-axis points upwards. In the left figure, the red path is
generated with the sweepline process described in Lemma 4.8. In the right
figure, by triangle inequality, $\lVert a_{1}a_{2}\rVert\leq\lVert
a_{1}^{\prime}a_{2}^{\prime}\rVert$, and $\beta_{0}+\alpha_{0}\leq\alpha$.

In Lemma 2.4, we showed that if $\lVert
qb\rVert\geq\mathchoice{\frac{\sin(\alpha)}{\cos(\theta)}}{(\sin(\alpha)/\cos(\theta))}{(\sin(\alpha)/\cos(\theta))}{(\sin(\alpha)/\cos(\theta))}\lVert
pq\rVert$, we can transform $pq$ into $pq^{\prime}$. If $pq^{\prime}$
intersects no obstacles, there exists a path $P$ from $A$ to $B$ such that
$\lVert P\rVert$ approximates $\lVert pq\rVert$, which also implies this
lemma. Otherwise, $pq^{\prime}$ intersects at least one obstacle. Without loss
of generality, we assume that $pq$ is aligned with the $x$-axis, where
$x(q)>x(p)$.

First, consider a horizontal ray $r=r(p,0)$, and rotate $r$ counter-clockwise
until the new ray, $r_{0}$, hits a sample point $a_{1}$ on the boundary of
some simplified obstacle (see Figure 7, left). Let the counter-clockwise
rotation from $r$ to $r_{0}$ be $\alpha_{0}$. With $\alpha_{i-1}$ and $a_{i}$
defined, let $a_{i+1}$ be the first sample point that is hit by rotating the
ray $r_{i}=r(a_{i},\sum\limits_{j=0}^{i-1}\alpha_{j})$ counter-clockwise. We
continue this process until either $r_{i}$ is parallel with direction
$r(k+1)$, or $r_{i}$ hits a sample point on $\partial B$. Let this final ray
be $r_{l}$, and $r_{l}$ hits $B$ at a sample point $a_{l}$. Indeed, if $r_{l}$
is in the direction $r(k+1)$, then $r(a_{l-1},k)$ hits $B$, and $a_{l}$ is a
propagated sample point.

Similarly, let $r^{\prime}=r(a_{1},\pi+\alpha_{0})$. We perform the same
process starting from $r^{\prime}$. Let $b_{1},...,b_{l^{\prime}}$ be the
sample points generated, where $b_{l^{\prime}}\in\partial A$, and let
$\beta_{0},...,\beta_{l^{\prime}-1}$ be the set of angles generated.

Let the intersection of $a_{1}b_{1}$ and $pq$ be $a_{0}=b_{0}$. We will show
the following.

$\displaystyle\sum_{i=0}^{i=l-1}\lVert
a_{i}a_{i+1}\rVert+\sum_{i=0}^{i=l^{\prime}-1}\lVert
b_{i}b_{i+1}\rVert\leq\mathchoice{\frac{\cos(\beta)}{\cos(\theta)}}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}\cdot\lVert
pq\rVert$ (1)

Observe that $\alpha_{0}+\beta_{0}\leq\alpha$, since the sweep-ray process
stops once the ray is parallel with direction $r(k+1)$. Let $q^{\prime}$ be
the point on $\partial B(b,q)$ such that $a_{0}q^{\prime}$ is parallel with
$r(k+1)$. Let $a_{i}^{\prime}$ be the point on $a_{0}q^{\prime}$, such that
$x(a_{i}^{\prime})=x(a_{i})$ (see Figure 7, right). By triangle inequality,
$\lVert a_{i}a_{i+1}\rVert\leq\lVert a^{\prime}_{i}a^{\prime}_{i+1}\rVert$. By
Lemma 2.2, $\lVert
a_{0}q\rVert<\mathchoice{\frac{\cos(\beta)}{\cos(\theta)}}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}\cdot\lVert
a_{0}q^{\prime}\rVert$. Combining the above, we have the following.

$\sum_{i=0}^{i=l-1}\lVert a_{i}a_{i+1}\rVert<\sum_{i=0}^{i=l-1}\lVert
a^{\prime}_{i}a^{\prime}_{i+1}\rVert<\mathchoice{\frac{\cos(\beta)}{\cos(\theta)}}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}\lVert
a_{0}q\rVert$

Using an analogous argument on the sample points
$\\{b_{0},...,b_{l^{\prime}}\\}$, and the fact that $\lVert pq\rVert=\lVert
pa_{0}\rVert+\lVert b_{0}q\rVert$, we proved Equality (1). We have shown that
there exist two sample points $a_{l}$ and $b_{l^{\prime}}$, such that
$\textbf{d}_{\textbf{S}}(a_{l},b_{l^{\prime}})\leq\mathchoice{\frac{\cos(\beta)}{\cos(\theta)}}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}\cdot\lVert
pq\rVert$, completing the proof.

######  Lemma 4.8.

Let $A$ and $B$ be two $0$-regions. Let $pq\subseteq P^{*}$, where
$p\in\partial A$, and $q\in\partial B$. If $\lVert
qb\rVert<\mathchoice{\frac{\sin(\alpha)}{\cos(\theta)}}{(\sin(\alpha)/\cos(\theta))}{(\sin(\alpha)/\cos(\theta))}{(\sin(\alpha)/\cos(\theta))}\cdot\lVert
pq\rVert$ and $\lVert pa\rVert<(\sin(\beta)/\cos(\theta))\cdot\lVert
pq\rVert$, where $a$ (resp. $b$) is a sample point adjacent to $p$ (resp.
$q$), then
$\textbf{d}_{\textbf{S}}(a,b)\leq(\sin(\alpha)+\sin(\beta))/(\cos(\theta)\sin(\theta))\cdot\lVert
pq\rVert$.

######  Proof 4.9.

Figure 8: In the left figure, by triangle inequality, $\lVert
aa^{\prime}\rVert+\lVert a^{\prime}b^{\prime}\rVert+\lVert b^{\prime}b\rVert$
is upperbounded by $\lVert au\rVert+\lVert ub\rVert$. In the middle and right
figure, fixing $b$, $\lVert au\rVert+\lVert bu\rVert$ strictly increases when
$a$ first moves to the boundary of the circular sector, and then moves along
the boundary to $p^{\prime}$ (paths marked in red).

If $ab$ overlaps no obstacles, $\textbf{d}_{\textbf{S}}(a,b)\leq\lVert
ab\rVert$. Therefore, we focus on the case where $ab$ overlaps at least one
obstacle. Let $a^{\prime}$ (resp. $b^{\prime}$) be the intersection of
$r_{a}=r(a,(k+1)\theta)$ (resp. $r_{b}=r(b,k\theta)$) and $pq$. See Figure 8,
left for the construction.

Observe that if $ab$ overlaps an obstacle $C$, then $C$ cannot overlap
$aa^{\prime}$ or $bb^{\prime}$. Assume the opposite that $C$ overlaps
$aa^{\prime}$. Since the regions are non-overlapping, and $pq\subseteq P^{*}$,
the sample point $v=sp(C,k\theta-\pi/2)$ would have to lie in
$\triangle{apa^{\prime}}$. Therefore, the ray $r(v,(k+1)\theta+\pi)$ hits $A$.
As a result, a propagated sample point is closer to $p$ than $a$,
contradicting the assumption that $a$ is the closest sample point to $p$.
Analogously, $C$ cannot overlap $bb^{\prime}$.

Consider the intersection $u$ of $r(a,k)$ and $r(b,(k+1)\theta+\pi)$. We argue
that $\textbf{d}_{\textbf{S}}(a,b)\leq\lVert au\rVert+\lVert bu\rVert$. Since
no simplified obstacles can intersect $r_{a}$ or $r_{b}$, we can build a
convex path $P$ from $a$ to $b$ within $\triangle{aub}$ circumventing all
obstacles. By Lemma 4.3, $\lVert P\rVert\leq\lVert au\rVert+\lVert bu\rVert$.

Let $q^{\prime}$ be the intersection of $r(p,(k+1)\theta)$ and
$r(q,k\theta+\pi/2)$, and let point $p^{\prime}$ be the intersection of
$r(q,k\theta+\pi)$ and $r(p,(k+1)\theta+\pi/2)$. Using analogous argument in
Lemma 2.6, we argue that $\lVert ab\rVert$ is maximised when $a=p^{\prime}$
and $b=q^{\prime}$. Since $a$ must be above $r(p,(k+1)\theta+\pi/2)$, below
$l_{t}(p)$ and within a distance $(\sin(\beta)/\cos(\theta))\cdot\lVert
pq\rVert$ from $p$, $a$ must lie in the smaller circular sector $S$ of the
disk $D(p,\lVert pp^{\prime}\rVert)$ bounded by $l_{t}(p)$ and $pp^{\prime}$.

With $b$ fixed, consider pushing $a$ along $r(a,k\theta+\pi)$ until $a$ lies
on the boundary $\partial S$ of $S$. $a$ is either above or below
$p^{\prime}q$; see Figure 8, middle and right, for an illustration of the
respective case. We will show that $\lVert au\rVert+\lVert bu\rVert$ strictly
increases throughout this process. Observe that by construction, pushing $a$
towards $\partial S$ strictly increases $\lVert au\rVert$ while $\lVert
bu\rVert$ remains unchanged.

Let $a^{\prime\prime}$ be the intersection of $r(a,k\theta+\pi)$ and $\partial
S$. If $a^{\prime\prime}$ lies on $D(p,\lVert pp^{\prime}\rVert)$, pushing
$a^{\prime\prime}$ towards $p^{\prime}$ increases both $\lVert
a^{\prime\prime}u\rVert$ and $\lVert bu\rVert$. If $a^{\prime\prime}$ lies on
$pp^{\prime}$, let $v$ be the intersection of $r(a^{\prime\prime},k+1)$ and
$qp^{\prime}$. Let $u^{\prime}$ be the intersection of $bu$ and $qp^{\prime}$.
We argue that $\lVert a^{\prime\prime}u\rVert+\lVert bu\rVert$ is maximised
when $a^{\prime\prime}=p^{\prime}$ and $u=u^{\prime}$. Specifically, the
length we gain ($\lVert p^{\prime}u^{\prime}\rVert-\lVert
a^{\prime\prime}u\rVert$) is more than the length we lose ($\lVert
uu^{\prime}\rVert$).

We argue that $\lVert p^{\prime}u^{\prime}\rVert-\lVert
a^{\prime\prime}u\rVert\geq\lVert uu^{\prime}\rVert$. Since
$\lozenge{a^{\prime\prime}vu^{\prime}u}$ is a parallelogram, $\lVert
a^{\prime\prime}u\rVert=\lVert vu^{\prime}\rVert$ and $\lVert
uu^{\prime}\rVert=\lVert a^{\prime\prime}v\rVert$. Therefore, we have that
$\lVert p^{\prime}u^{\prime}\rVert-\lVert a^{\prime\prime}u\rVert-\lVert
uu^{\prime}\rVert=\lVert p^{\prime}v\rVert-\lVert a^{\prime\prime}v\rVert$. By
construction, $\triangle{vp^{\prime}a^{\prime\prime}}$ is a right triangle
with $p^{\prime}v$ as the hypotenuse. As a result, $\lVert
p^{\prime}v\rVert\geq\lVert a^{\prime\prime}v\rVert$, and $\lVert
p^{\prime}u^{\prime}\rVert-\lVert a^{\prime\prime}u\rVert\geq\lVert
uu^{\prime}\rVert$. Therefore, with $b$ fixed, $\lVert au\rVert+\lVert
bu\rVert$ is maximised when $a=p^{\prime}$. Using an analogous argument by
fixing $a$ at $p^{\prime}$, we have that $\lVert ab\rVert$ is maximised when
$a=p^{\prime}$ and $b=q^{\prime}$. Combining the above arguments and Lemma
2.6, we have that

$\displaystyle\textbf{d}_{\textbf{S}}(a,b)\leq\lVert au\rVert+\lVert
bu\rVert\leq\lVert p^{\prime}c\rVert+\lVert
q^{\prime}c\rVert=\frac{\sin(\alpha)+\sin(\beta)}{\cos(\theta)\sin(\theta)}\cdot\lVert
pq\rVert.$

We combine Lemma 4.6 and Lemma 4.8 to obtain a bound on the path length where
$p$ and $q$ both lie on $0$-regions. Note that when two points $p$ and $a$ lie
on the boundary of the same 0-region, $\textbf{d}_{\textbf{S}}(a,p)=0$.

######  Lemma 4.10.

Let $A$ and $B$ be two convex 0-regions. Let $pq\subseteq P^{*}$, where
$p\in\partial A$ and $q\in\partial B$. There exists a pair of sample points
$a\in A$ and $b\in B$, such that
$\textbf{d}_{\textbf{S}}(p,a)+\textbf{d}_{\textbf{S}}(a,b)+\textbf{d}_{\textbf{S}}(b,q)\leq\max\\{\mathchoice{\frac{\cos(\beta)}{\cos(\theta)}}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))},(\sin(\alpha)+\sin(\beta))/(\cos(\theta)\sin(\theta))\\}\cdot\lVert
pq\rVert$.

####  4.3.2 Case 2: $pq$ connects two obstacles

Using Fact 2, we know that if $pq$ connects two obstacles, then $pq$ must
coincide with a common tangent of $A$ and $B$. When two obstacles are close,
$p$ (and $q$) may be very far from its adjacent sample points. Hence, we need
the tangent sample points when two obstacles are close (connected via a
trapezoidal map). We now show that if $p$ and $q$ lie on obstacles, an
approximate path exists in $\mathcal{G}\in\mathcal{B}$.

######  Lemma 4.11.

Let $A$ and $B$ be two convex obstacles. Let $pq\subseteq P^{*}$, where
$p\in\partial A$ and $q\in\partial B$. There exists a pair of sample points
$a\in A$ and $b\in B$, such that
$\textbf{d}_{\textbf{S}}(p,a)+\textbf{d}_{\textbf{S}}(a,b)+\textbf{d}_{\textbf{S}}(b,q)\leq\mathchoice{\frac{1}{\cos(\theta)}}{(1/\cos(\theta))}{(1/\cos(\theta))}{(1/\cos(\theta))}\cdot\lVert
pq\rVert$.

######  Proof 4.12.

Figure 9: In the left figure, if an obstacle $C$ overlaps $ab$ and $r(a,k)$,
then there must exists a point $c\in C$ lying in $\triangle{app^{\prime}}$.
There exists a propagated sample point (red) that is closer to $p$ than $a$
is. Otherwise, in the right figure, there exists a convex path $P$ (shown in
blue) from $a$ to $b$, and $\lVert P\rVert$ is at most $\lVert au\rVert+\lVert
ub\rVert$.

We first observe that if $A$ and $B$ are connected using the trapezoidal map,
then both tangent sample points $p$ and $q$ were added by construction.
Clearly, $\textbf{d}_{\textbf{S}}(p,q)=\lVert
pq\rVert\leq(1/\cos(\theta))\cdot\lVert pq\rVert$. Therefore, we consider the
scenario when $A$ and $B$ are not connected using the trapezoidal map. Without
loss of generality, let $pq$ lie on the $y$-axis with $y(q)>y(p)$, and let
$pq$ lie between $r(p,k)$ and $r(p,k+1)$.

If both $A$ and $B$ lie on the same side of the line through $pq$, we assume
that without loss of generality, they lie on the left side (see Figure 9). Let
$a$ be the closest sample point of $p$, and let $b$ be the closest sample
point of $q$, such that $y(b)<y(q)$ and $y(a)>y(p)$. Observe that $a$ must be
above $r(p,k+1)$, and similarly, $b$ must be below $r(q,k\theta+\pi)$.

Since $a$ is the closest sample point to $p$ and $b$ is the closest sample
point of $q$, we have that $\textbf{d}_{\textbf{S}}(p,a)=\lVert pa\rVert$ and
$\textbf{d}_{\textbf{S}}(b,q)=\lVert bq\rVert$. If $ab$ overlaps no obstacles,
$\textbf{d}_{\textbf{S}}(a,b)\leq\lVert ab\rVert$. Since we do not need to
take a detour from $a$ to $b$, it is sufficient to find an upperbound on
$\lVert pa\rVert+\lVert ab\rVert+\lVert bq\rVert$. Therefore, we focus on the
worse case where $ab$ overlaps at least one obstacle. Let $u$ be the
intersection of $r(a,k)$ and $r(b,(k+1)\theta+\pi)$. It remains true that if
an obstacle $C$ overlaps $ab$ and $r(a,k)$ simultaneously, there must exist a
propagated sample point on $A$ that is closer to $p$ than $a$ is. Therefore
the arguments in Lemma 4.8 apply, and $\textbf{d}_{\textbf{S}}(a,b)\leq\lVert
au\rVert+\lVert ub\rVert$.

Figure 10: In the left figure, $\textbf{d}_{\textbf{S}}(a,b)$ is maximised
when $a$ and $b$ lie on $pv$ and $qv$, respectively, and $\lVert
pa\rVert+\textbf{d}_{\textbf{S}}(a,b)+\lVert qb\rVert$ (red) is at most
$\lVert pv\rVert+\lVert qv\rVert$ (blue). In the right figure, segments with
the same color have equal lengths.

Let $v$ be the intersection of $r(p,k+1)$ and $r(q,k\theta+\pi)$ (see Figure
10, left). We argue that $\lVert pa\rVert+\lVert au\rVert+\lVert
ub\rVert+\lVert bq\rVert$ is maximised when $a$ lies on $r(p,k+1)$ and $b$
lies on $r(q,k\theta+\pi)$. Then, when both $a$ and $b$ lie on their
respective rays, we show that the total length $\lVert pa\rVert+\lVert
au\rVert+\lVert ub\rVert+\lVert bq\rVert$ is at most $\lVert pv\rVert+\lVert
qv\rVert$. To do this, we partition the latter and show that each partition
(or two partitions combined) pays for a segment in the former.

By constructing the sample points, $a$ and $b$ must reside in
$\triangle{pqv}$. The segment $ab$ must lie between the directions $r(k)$ and
$r(k+1)$, as otherwise, $A$ and $B$ are connected via the trapezoidal map. As
a result, $y(b)>y(a)$, and $u$ is to the right of $ab$. See Figure 10, right
for the following definitions. Let $u^{\prime}$ be the intersection of
$r(b,k\theta+\pi)$ and $r(a,k+1)$. Observe that $\lVert
bu^{\prime}\rVert=\lVert au\rVert$ and $\lVert au^{\prime}\rVert=\lVert
bu\rVert$. Let $b^{\prime}$ (resp. $b^{\prime\prime}$) be the intersection of
$r(b,k+1)$ (resp. $r(a,k+1)$) and $qv$. Both $b^{\prime}$ and
$b^{\prime\prime}$ are well-defined, since $r(b,k+1)$, $r(a,k+1)$, and
$r(p,k+1)$ are parallel. The points $a^{\prime}$ and $a^{\prime\prime}$ are
defined similarly.

Using the triangle inequality, we have that $\lVert qb\rVert\leq\lVert
qb^{\prime}\rVert+\lVert bb^{\prime}\rVert$. We observe that $\lVert
b^{\prime}b^{\prime\prime}\rVert=\lVert au\rVert$ and $\lVert
bb^{\prime}\rVert=\lVert va^{\prime\prime}\rVert$. Combining the above facts,
if we focus on $\lVert qb\rVert+\lVert bu\rVert$, we have

$\displaystyle\lVert qb\rVert+\lVert bu\rVert$ $\displaystyle\leq\lVert
qb^{\prime}\rVert+\lVert b^{\prime}b\rVert+\lVert bu\rVert$
$\displaystyle\triangleright\text{Triangle inequality}$ $\displaystyle=\lVert
qb^{\prime}\rVert+\lVert a^{\prime}v\rVert.$
$\displaystyle\triangleright\text{$\lozenge{b^{\prime}ua^{\prime}v}$ is a
parallelogram}$ (1)

Similarly,

$\displaystyle\lVert pa\rVert+\lVert au\rVert$ $\displaystyle\leq\lVert
pa^{\prime}\rVert+\lVert a^{\prime}a\rVert+\lVert au\rVert\leq\lVert
pa^{\prime}\rVert+\lVert b^{\prime}v\rVert.$ (2)

Combining (1) and (2), and the fact that
$\textbf{d}_{\textbf{S}}(a,b)\leq\lVert au\rVert+\lVert ub\rVert$, we have the
following.

$\displaystyle\textbf{d}_{\textbf{S}}(p,a)+\textbf{d}_{\textbf{S}}(a,b)+\textbf{d}_{\textbf{S}}(b,q)$
$\displaystyle\leq\lVert pa\rVert+\lVert au\rVert+\lVert ub\rVert+\lVert
bq\rVert$ $\displaystyle\leq\lVert pv\rVert+\lVert qv\rVert$
$\displaystyle\leq\sec\left(\frac{\theta}{2}\right)\cdot\lVert pq\rVert$
$\displaystyle\triangleright\text{Lemma\leavevmode\nobreak\
\ref{lem:boundary_over_segment}}$

Figure 11: In the left figure, if an obstacle $C$ overlaps $ab$ and
$r(a,k+1)$, then a propagated sample point (red) must be closer to $p$ than
$a$ is. In the right figure, two convex paths (red) can be generated in
$\triangle{auu_{a}}$ and $\triangle{buu_{b}}$.

Using analogous arguments, if $A$ and $B$ lie on the opposite sides of $pq$
(see Figure 11, left), and an obstacle $C$ overlaps $ab$, part of $C$ must lie
in either triangle $\triangle{pau}$ or $\triangle{qbu}$ (not both).

Without loss of generality, assume that $C$ overlaps $\triangle{pau}$. If $C$
additionally overlaps $r(a,k+1)$, a propagated sample point $d$ is closer to
$q$ than $b$, contradicting the assumption that $b$ is the closest sample
point. An analogous argument applies when $C$ overlaps $\triangle{qbu}$.
Therefore if $C$ overlaps $ab$, then $C$ must reside in the either
$\triangle{a}=\triangle{auu_{a}}$ or $\triangle{b}=\triangle{buu_{b}}$, where
$u_{b}$ (resp. $u_{a}$) is the intersection of $r(b,(k+1)\theta+\pi)$ (resp.
$r(a,k+1)$) and $ab$.

We can construct two convex paths $P_{a}$ and $P_{b}$ (see Figure 11, right);
$P_{a}$ resides in $\triangle{a}$ and connects $a$ to $u$, and $P_{b}$ resides
in $\triangle{b}$ and connects $b$ to $u$. By Lemma 4.3, we have that

$\displaystyle\textbf{d}_{\textbf{S}}(a,b)$ $\displaystyle\leq\lVert
P_{a}\rVert+\lVert P_{a}\rVert$ $\displaystyle\leq\lVert au_{a}\rVert+\lVert
u_{a}u_{b}\rVert+\lVert u_{b}b\rVert.$ (1)

Figure 12: Segments with matching color have equal length. Every segment in
$\\{pa_{r},au_{a},u_{a}u_{b},u_{b}b\\}$ can be payed for by either segment(s)
on $pv$ or segment(s) on $qv$.

We now upperbound (1). Let $v$ be the intersection of $r(q,k\theta+\pi)$ and
$r(p,k\theta+2\beta)$ (see Figure 12). Let point $a_{r}$ be the reflection of
$a$ along $pq$. Observe that since $a$ is above $r(p,k\theta)$, $a_{r}$ must
be above $r(p,k\theta+2\beta)$, and $\lVert pa_{r}\rVert=\lVert pa\rVert$. Let
$a^{\prime}$ (resp. $b^{\prime}$) be the intersection of
$r(a_{r},k\theta+\pi)$ (resp. $r(b,k\theta+2\beta)$.

Using an analogous charging argument, we have that

$\displaystyle\lVert au_{a}\rVert+\lVert u_{a}u_{b}\rVert+\lVert
u_{b}b\rVert\leq\lVert pv\rVert+\lVert
qv\rVert\leq\frac{1}{\cos(\beta)}\cdot\lVert pq\rVert.$

Combining with the bound on $\textbf{d}_{\textbf{S}}(a,b)$ in the case that
$a$ and $b$ lie on the same side of $pq$, we have that

$\displaystyle\textbf{d}_{\textbf{S}}(p,a)+\textbf{d}_{\textbf{S}}(a,b)+\textbf{d}_{\textbf{S}}(b,q)$
$\displaystyle=\lVert pa\rVert+\textbf{d}_{\textbf{S}}(a,b)+\lVert bq\rVert$
$\displaystyle\leq\max\left\\{\sec\left(\frac{\theta}{2}\right),\frac{1}{\cos(\beta)}\right\\}\cdot\lVert
pq\rVert\leq\frac{1}{\cos(\theta)}\cdot\lVert pq\rVert$

####  4.3.3 Case 3: $pq$ connects a 0-region and an obstacle

In this section, we prove that if $pq$ connects an obstacle $A$ and a
$0$-region $B$, there is a path $P$ that approximate $pq$.

######  Lemma 4.13.

Let $A$ be a convex obstacle and let $B$ be a convex $0$-region. Let
$pq\subseteq P^{*}$, where $p\in\partial A$ and $q\in\partial B$. There exists
a pair of sample points $a\in A$ and $b\in B$, such that
$\textbf{d}_{\textbf{S}}(p,a)+\textbf{d}_{\textbf{S}}(a,b)+\textbf{d}_{\textbf{S}}(b,q)\leq\mathchoice{\frac{\cos(\beta)}{\cos(\theta)}}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}\cdot\lVert
pq\rVert$.

######  Proof 4.14.

Figure 13: In the left figure, $ab$ is parallel to the direction $r(k)$. An
obstacle $C$ overlapping $ab$ generates a propagated sample point $v^{\prime}$
(red) closer to $q$ than $b$. In the right figure, $\lVert pa\rVert+\lVert
ab\rVert$ is at most $\lVert pq^{\prime}\rVert$ since $ab$ (red) is at most as
long as $ac$ (blue), and $\lVert pa\rVert+\lVert ac\rVert\leq\lVert
pq^{\prime}\rVert$.

Let $pq$ be aligned with the $y$-axis, such that $y(q)>y(p)$. If $pq$ is in
some direction $r(k)$, then both $p$ and $q$ are sample points, and
$(p,q)\in\mathcal{E}$. Therefore, we consider the case where $pq$ is between
direction $r(k)$ and $r(k+1)$. Let $\beta$ (resp. $\alpha$) be the acute angle
between $r(p,k)$ (resp. $r(p,k+1)$) and $pq$ (see Figure 13).

Let $a\in\partial A$ be the first sample point in a counter-clockwise order
after $p$. Let $b\in\partial B$ be the first sample point in a clockwise order
after $q$. Let $q^{\prime}$ be the intersection of $r(p,k+1)$ and
$r(q,k\theta+\pi/2)$. By convexity and the placement of our sample points, $a$
must be above $r(p,k+1)$, and $b$ must lie below $r(q,k\theta+\pi/2)$.

If $ab$ is parallel with $r(k)$, then $ab$ cannot overlap any obstacle $C$.
Otherwise, there exists a sample point $v\in\partial C$ in the direction of
$r(k\theta-\pi/2)$ (see Figure 13, left). Since $v$ must lie on or to the left
of $pq$, $r(v,k)$ generates a propagated sample point $v^{\prime}$ on
$\partial B(b,q)$, and $v^{\prime}$ is closer to $q$ than $b$ is,
contradicting the assumption that $b$ is the closest sample point. Therefore,
$\textbf{d}_{\textbf{S}}(p,a)+\textbf{d}_{\textbf{S}}(a,b)\leq\lVert
pa\rVert+\lVert ab\rVert$.

To bound $\lVert pa\rVert+\lVert ab\rVert$, we observe that $\lVert
pa\rVert+\lVert ab\rVert$ is maximised when $b$ lies on $r(q,k\theta+\pi/2)$
(see Figure 13, right). Let $c$ be the intersection of $r(a,k+1)$ and
$r(q,k\theta+\pi/2)$. Observe that $ab$ is perpendicular to $pq^{\prime}$. We
have that $\lVert ab\rVert\leq\lVert ac\rVert$, since $ab$ is a leg of the
right triangle $\triangle{abc}$, and $ac$ is the hypotenuse. Using the
arguments in Lemma 4.10, $\lVert pa\rVert+\lVert ac\rVert\leq\lVert
pq^{\prime}\rVert=\mathchoice{\frac{\cos(\beta)}{\cos(\theta)}}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}\cdot\lVert
pq\rVert$. We thus have a path from $p$ to $q$ via $a$ and $b$ of length

$\displaystyle\lVert pa\rVert+\lVert
ab\rVert+\textbf{d}_{\textbf{S}}(b,q)=\lVert pa\rVert+\lVert
ab\rVert\leq\lVert pa\rVert+\lVert ac\rVert\leq\lVert
pq^{\prime}\rVert\leq\mathchoice{\frac{\cos(\beta)}{\cos(\theta)}}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}\cdot\lVert
pq\rVert.$

Figure 14: In the left and middle figure, the length of both red paths are
upperbounded by the length of the blue path. In the right figure, $\lVert
a^{\prime\prime}u^{\prime}\rVert>\lVert a^{\prime\prime}b^{\prime}\rVert$ by
construction.

If $ab$ is not parallel with $r(k+1)$, the ray $r(a,k)$ must intersect $pq$ at
some point $v$ ($a$ does not propagate to $b$). For the same reasons as
before, an obstacle overlaps neither $r(a,k)$ nor $pq$. Let
$q^{\prime\prime}=q$. Consider sliding $q^{\prime\prime}$ towards $a$ along
the concatenated polygonal chain $qv\circ va$ until the ray
$r(q^{\prime\prime},k+1)$ touches $b$ (see Figure 14). Observe that
$r(q^{\prime\prime},k+1)$ cannot intersect an obstacle during the slide.
Indeed, if $r(q^{\prime\prime},k+1)$ touches an obstacle $O$ at point $o$, $o$
must be a sample point with respect to the direction $r((k+1)\theta-\pi/2)$,
and $o$ propagates to $b$ with the ray $r(o,k+1)$. Let $a^{\prime}$ (resp.
$a^{\prime\prime}$) be the point on $pu$ such that $a^{\prime}v$ (resp.
$a^{\prime\prime}q$) is parallel to $r(k)$. Let $b^{\prime}$ be the
intersection of $r(q^{\prime\prime},k+1)$ and $a^{\prime\prime}q$. Let
$b^{\prime\prime}$ be the point on $a^{\prime\prime}q$ such that
$ab^{\prime\prime}$ is parallel to $r(k+1)$.

When we stop the sliding, either 1) $q^{\prime\prime}$ is on $av$, or 2)
$q^{\prime\prime}$ is on $qv$ (see Figure 14, left and middle, respectively).
In order to avoid obstacles, we have to take a detour from $a$ to $b$. In both
cases, we argue that the length of the detour is at most $\lVert
pa^{\prime\prime}\rVert+\lVert a^{\prime\prime}b^{\prime}\rVert+\lVert
b^{\prime}b\rVert$. In case 1, the maximum length of the detour we must take
is $d_{1}=\lVert pa\rVert+\lVert aq^{\prime\prime}\rVert+\lVert
q^{\prime\prime}b\rVert$. We use a charging argument: $\lVert
b^{\prime}b^{\prime\prime}\rVert$ pays for $\lVert aq^{\prime\prime}\rVert$,
and $\lVert a^{\prime}a^{\prime\prime}\rVert$ pays for $\lVert
b^{\prime}q^{\prime\prime}\rVert$. $\lVert aa^{\prime}\rVert=\lVert
b^{\prime\prime}a^{\prime\prime}\rVert$, and by triangle inequality, $\lVert
pa\rVert\leq\lVert pa^{\prime}\rVert+\lVert a^{\prime}a\rVert$. Therefore,
$d_{1}\leq\lVert pa^{\prime\prime}\rVert+\lVert
a^{\prime\prime}b^{\prime}\rVert+\lVert b^{\prime}b\rVert$.

In case 2, the maximum length of the detour is $d_{2}=\lVert pa\rVert+\lVert
av\rVert+\lVert vq^{\prime\prime}\rVert+\lVert q^{\prime\prime}b\rVert$. Let
$v^{\prime\prime}$ be the point on $pu$ such that
$v^{\prime\prime}q^{\prime\prime}$ is parallel to $r(k)$. Let $v^{\prime}$ be
the intersection of $r(v,k+1)$ and $v^{\prime\prime}q^{\prime\prime}$. Let $c$
be the point on $b^{\prime}b^{\prime\prime}$ such that $vc$ is parallel to
$r(k+1)$. Using analogous argument, $\lVert
a^{\prime\prime}v^{\prime\prime}\rVert$ pays for $\lVert
b^{\prime}q^{\prime\prime}\rVert$, and $\lVert
b^{\prime\prime}v^{\prime\prime}\rVert$ pays for $\lVert av\rVert$. By
triangle inequality, $\lVert a^{\prime\prime}b^{\prime\prime}\rVert+\lVert
pa^{\prime}\rVert$ pays for $\lVert ap\rVert$, and $\lVert
b^{\prime}v^{\prime\prime}\rVert+\lVert a^{\prime}v^{\prime\prime}\rVert$ pays
for $\lVert vq^{\prime\prime}\rVert$. For both cases, we have that

$\displaystyle\lVert pa\rVert+\textbf{d}_{\textbf{S}}(a,b)\leq\lVert
pa^{\prime\prime}\rVert+\lVert a^{\prime\prime}b^{\prime}\rVert+\lVert
b^{\prime}b\rVert.$ (1)

Next, we argue that $\lVert pa^{\prime\prime}\rVert+\lVert
a^{\prime\prime}b^{\prime}\rVert+\lVert b^{\prime}b\rVert$ is at most $\lVert
pu\rVert$ (see Figure 14, right). Let $u^{\prime}$ be the point on $pu$ such
that $b^{\prime}u^{\prime}$ is parallel to $qu$. By construction, $pu$ is
parallel to $r(k\theta+\pi/2)$, and $a^{\prime\prime}b^{\prime}$ is parallel
to $r(k\theta)$. The triangle
$\triangle{b^{\prime}u^{\prime}a^{\prime\prime}}$ is therefore a right
triangle with $a^{\prime\prime}u^{\prime}$ as the hypotenuse. $\lVert
bb^{\prime}\rVert=\lVert uu^{\prime}\rVert$, and therefore we have that

$\displaystyle\lVert pa^{\prime\prime}\rVert+\lVert
a^{\prime\prime}b^{\prime}\rVert+\lVert b^{\prime}b\rVert<\lVert
pa^{\prime\prime}\rVert+\lVert a^{\prime\prime}u^{\prime}\rVert+\lVert
u^{\prime}u\rVert=\lVert pu\rVert.$ (2)

Combining (1), (2), Lemma 2.2, and the fact that $bq$ lies in a 0-region, we
complete the proof with the following.

$\displaystyle\textbf{d}_{\textbf{S}}(p,a)+\textbf{d}_{\textbf{S}}(a,b)+\textbf{d}_{\textbf{S}}(b,q)=\lVert
pa\rVert+\textbf{d}_{\textbf{S}}(a,b)\leq\lVert
pu\rVert\leq\mathchoice{\frac{\cos(\beta)}{\cos(\theta)}}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}\cdot\lVert
pq\rVert$

###  4.4 The quality of the path

In Lemma 4.10, 4.11, and 4.13, we have shown that for every segment $pq$ in
Case 1-3 in Fact 2, either there exists a path $P\subseteq\mathcal{E}$ such
that $\textbf{w}(P)$ approximates $\lVert pq\rVert$, or there exist two sample
points $a$ and $b$ such that
$\textbf{d}_{\textbf{S}}(p,a)+\textbf{d}_{\textbf{S}}(a,b)+\textbf{d}_{\textbf{S}}(b,q)$
approximates $\lVert pq\rVert$. Taking the maximum ratio in the three lemmas,
we have the following.

$\displaystyle\textbf{d}_{\textbf{S}}(p,a)+\textbf{d}_{\textbf{S}}(a,b)+\textbf{d}_{\textbf{S}}(b,q)$
$\displaystyle\leq\max\left\\{\mathchoice{\frac{\cos(\beta)}{\cos(\theta)}}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))}{(\cos(\beta)/\cos(\theta))},\mathchoice{\frac{1}{\cos(\theta)}}{(1/\cos(\theta))}{(1/\cos(\theta))}{(1/\cos(\theta))},\frac{\sin(\alpha)+\sin(\beta)}{\cos(\theta)\sin(\theta)}\right\\}\cdot\lVert
pq\rVert$
$\displaystyle\leq\frac{2\sin(\frac{\theta}{2})}{\cos(\theta)\sin(\theta)}\cdot\lVert
pq\rVert$

For a Case 4 segment $\partial A(p,q)$, where both $p$ and $q$ lies on the
obstacle $A$, assume without loss of generality that $p$ occurs before $q$ in
$P^{*}$, and let $pq=\partial A(p,q)$.

If $\partial A(p,q)$ contains no sample point, then assume that the optimal
path uses segment $p^{\prime}p$ to reach $A$, and $qq^{\prime}$ to leave $A$.
We argue that there exists an approximate path $P$ that approximates $\lVert
p^{\prime}p\rVert+\lVert\partial A(p,q)\rVert+\lVert qq^{\prime}\rVert$. Let
$a$ (resp. $b$) be the closest sample point to $p$ (resp. $q$), such that
$\partial A(p,q)\subseteq\partial A(a,b)$. In Lemma 4.10, 4.11, and 4.13, we
have payed for a path $P_{p}\subseteq\mathcal{E}$ from $p^{\prime}$ to $p$
though $a$ and a path $P_{q}\subseteq\mathcal{E}$ from $q$ to $q^{\prime}$
through $b$. Since there is no sample point on $\partial A(p,q)$, instead of
going from $a$ to $p$ and $q$ to $b$, we take the path $ab$ directly. The
unused cost of $\textbf{d}_{\textbf{S}}(a,p)$ and
$\textbf{d}_{\textbf{S}}(q,b)$ pays for $\lVert ab\rVert$.

Let $p_{\perp}$ (resp. $q_{\perp}$) be the orthogonal projection of $p$ (resp.
$q$) on $ab$. Clearly, $\lVert\partial A(a,p)\rVert\geq\lVert
ap_{\perp}\rVert$ and $\lVert\partial A(q,b)\rVert\geq\lVert
bq_{\perp}\rVert$. By Lemma 4.3, $\lVert\partial
A(p,q)\rVert\leq\mathchoice{\sec(\frac{\theta}{2})}{\sec(\theta/2)}{\sec(\theta/2)}{\sec(\theta/2)}\cdot\lVert
p_{\perp}q_{\perp}\rVert$. Therefore, we connect $P_{p}$ and $P_{q}$ using
$ab$ to generate a path $P$, and we have that

$\displaystyle\lVert
P\rVert\leq\frac{2\sin(\frac{\theta}{2})}{\cos(\theta)\sin(\theta)}\cdot(\lVert
p^{\prime}p\rVert+\lVert\partial A(p,q)\rVert+\lVert qq^{\prime}\rVert).$

If $\partial A(p,q)$ contains at least one sample point $\\{a,...,b\\}$, then
by Lemma 4.3, we have that

$\displaystyle\textbf{d}_{\textbf{S}}(p,a)+\textbf{d}_{\textbf{S}}(a,b)+\textbf{d}_{\textbf{S}}(b,q)\leq\sec\left(\frac{\theta}{2}\right)\cdot\lVert
pq\rVert.$

Bose and van Renssen [6] showed that in an environment with polygonal
obstacles, a $\Theta$-graph has a spanning ratio of at most
$r_{\theta}=1+2\sin(\theta/2)/(\cos(\theta/2)-\sin(\theta/2))$. We also need
to apply the factor to traverse the boundaries of convex obstacles to account
for the difference compared to the boundaries of simplified obstacles, as in
Lemma 4.3. We obtain the following bound when $\theta<\pi/12$.

$\displaystyle\frac{2\sin(\frac{\theta}{2})}{\cos(\theta)\sin(\theta)}\cdot\left(1+\frac{2\sin(\frac{\theta}{2})}{\cos(\frac{\theta}{2})-\sin(\frac{\theta}{2})}\right)\cdot\frac{2\sin(\frac{\theta}{2})}{\sin(\theta)}\leq\frac{1}{1-\sin(2\theta)}$

Given an approximation error $0<\varepsilon<1$, we compute the parameter
$0<\theta<\pi/12$ as the following.

$\displaystyle\frac{1}{1-\sin(2\theta)}\leq
1+\varepsilon\implies\theta\leq\frac{\sin^{-1}(\frac{\varepsilon}{1+\varepsilon})}{2}$

######  Lemma 4.15.

In $\mathcal{B}$, there exists a path $P\subseteq\mathcal{E}$ between any pair
of sample points $(a,b)$ such that
$\textbf{w}(P)\leq(1+\varepsilon)\cdot\textbf{d}(a,b)$.

###  4.5 Finding a shortest path amidst $0$-regions and obstacles

Given the data structure $\mathcal{B}=\\{\mathcal{M}(k)\mid\forall
k\in[0,2\pi/\theta),k\in\mathbb{Z}\\}\cup\\{\mathcal{G},\mathcal{G}_{\Theta}\\}$,
a point $s$, and a point $t$, we query the approximate shortest path from $s$
to $t$ using Algorithm 4.

Algorithm 4 Query $s$-$t$ weighted shortest path amidst 0-regions and
obstacles

This algorithm takes as input a data structure
$\mathcal{B}=\\{\mathcal{M}(k)\mid\forall
k\in[0,2\pi/\theta),k\in\mathbb{Z}\\}\cup\\{\mathcal{G},\mathcal{G}_{\Theta}\\}$
storing a set of 0-regions and a set of obstacles, a point $s$, and a point
$t$. It outputs an $(1+\varepsilon)$-approximated weighted shortest path from
$s$ to $t$. In Step 2 and Step 3, this algorithm shows how to add $s$ to
$\mathcal{B}$, and the same operations are used to add $t$.

  1. 1.

Add $s$ and $t$ to $\mathcal{V}$.

  2. 2.

For each trapezoidal map $\mathcal{M}(k)$, do the following for point $s$.

    1. (a)

Query the face $F$ containing $s$. Let $F$ be adjacent to $A$ and $B$, $A\neq
B$.

    2. (b)

Add the propagated sample points $a\in A$ and $b\in B$—which are generated by
$r(s,k)$ and $r(s,k\theta+\pi)$, respectively—to $\mathcal{V}$.

    3. (c)

If $A$ is a $0$-region, add $e=(s,ak(A))$ and set
$\textbf{w}(e)=\textbf{d}(s,A)$. Do the same for $B$.

    4. (d)

If $A$ is an obstacle, add $e=(a,s)$, and set $\textbf{w}(e)=\lVert as\rVert$.
Compute the common tangents $T$ of $s$ and $A$. For each common tangent $t\in
T$ touching $A$ at point $a^{\prime}$, add $a^{\prime}$ to $\mathcal{V}$. Do
the same for $B$.

  3. 3.

Add $s$ and the additional sample points generated in Step 2 to
$\mathcal{G}_{\Theta}$. For each newly added point $s^{\prime}$, using
$s^{\prime}$ as the apex, we construct a set of disjoint cones with angle
$\theta$. For each point $p$ closest to $s^{\prime}$ in each cone, add
$e=(s^{\prime},p)$ to $\mathcal{E}$, and set $\textbf{w}(e)=\lVert
s^{\prime}p\rVert$. For every existing vertex $p\in\mathcal{G}_{\Theta}$, and
every existing edge $(p,q)\in\mathcal{E}_{\Theta}$. If $s^{\prime}$ is closer
to $p$ than $q$ is, add $e=(s^{\prime},p)$ to $\mathcal{E}$, and set
$\textbf{w}(e)=\lVert s^{\prime}p\rVert$.

  4. 4.

Use Dijkstra’s shortest path algorithm to compute a path $P^{\prime}$ from $s$
to $t$ in $\mathcal{G}$. Transform $P^{\prime}$ into a path $P$ in the
original environment and return $P$.

Using the query algorithm, we treat both $s$ and $t$ as convex obstacles with
no interior. This preserves the properties of the trapezoidal maps and the
$\Theta$-graph, and enables us to apply the earlier lemmas.

####  4.5.1 Analysis

We now analyse the query time. In Step 2, we perform a set of operations for
each of the $O(1/\varepsilon)$ trapezoidal maps. In Step 2a, it takes
$O(\log(n/\varepsilon))$ time to find the face containing $s$. In Step 2b, it
takes $O(\log N)$ time to use a binary search to compute the intersection of a
ray and a convex boundary with $O(N)$ complexity. In Step 2c, it takes $O(\log
N)$ time to compute the distance between $s$ and a convex region using the
algorithm by Edelsrunner [15]. In Step 2d, it takes $O(\log N)$ time to
compute the common tangent using the algorithms by Kirkpatrick and Snoeink
[19], and Guibas et al. [18]. In total, Step 2 takes
$O((\log(n/\varepsilon)+\log N)/\varepsilon)$ time.

Inserting $s$ into $\mathcal{B}$ generates a constant number of sample points.
In Step 3, for each additional sample point $s^{\prime}$, it takes
$O(n/\varepsilon^{3})$ time to find the closest point of $s^{\prime}$ in each
cone, and at the same time, check if $s^{\prime}$ is closest to any point $p$.
In Step 4, it takes $O(|\mathcal{E}|+|\mathcal{V}|\log|\mathcal{V}|)$ to run
Dijkstra’s shortest path algorithm. There are $O(n/\varepsilon^{2})$ vertices,
and $O(n/\varepsilon^{3})$ edges, therefore Dijkstra’s algorithm takes
$O(n/\varepsilon^{3}+(n/\varepsilon^{2})\log(n/\varepsilon))$ time to return a
path $P^{\prime}$ comprised of at most $O(n/\varepsilon^{3})$ edges. It takes
$O(n/\varepsilon^{3}+N)$ time to transform $P^{\prime}$ into a path $P$ in the
environment by traversing the boundaries of the regions.

In total, it takes
$O(N+n/\varepsilon^{3}+(n/\varepsilon^{2})\log(n/\varepsilon)+(\log
N)/\varepsilon)$ time to query the approximate $s$-$t$ shortest path.
Combining the above analysis with Lemma 4.2, 4.10, 4.11, and 4.13, we have the
following.

See 1.3

## References

  * [1] Lyudmil Aleksandrov, Anil Maheshwari, and Jörg-Rüdiger Sack.  Approximation algorithms for geometric shortest path problems.  In Proceedings of the Thirty-second Annual ACM Symposium on Theory of Computing, pages 286–295, New York, NY, USA, May 2000. Association for Computing Machinery.
  * [2] Lyudmil Aleksandrov, Anil Maheshwari, and Jörg-Rüdiger Sack.  Determining approximate shortest paths on weighted polyhedral surfaces.  Journal of the ACM, 52(1):25–53, January 2005.
  * [3] Helmut Alt and Michael Godau.  Computing the Fréchet distance between two polygonal curves.  International Journal of Computational Geometry & Applications, 05:75–91, March 1995.
  * [4] Prosenjit Bose, Jean-Lou de Carufel, Pat Morin, André van Renssen, and Sander Verdonschot.  Towards tight bounds on theta-graphs: More is not always better.  Theoretical Computer Science, 616:70–93, February 2016.
  * [5] Prosenjit Bose, Guillermo Esteban, David Orden, and Rodrigo I. Silveira.  On approximating shortest paths in weighted triangular tessellations.  Artificial Intelligence, 318:103898, May 2023.
  * [6] Prosenjit Bose and André van Renssen.  Spanning properties of Yao and theta-graphs in the presence of constraints.  International Journal of Computational Geometry & Applications, 29(02):95–120, June 2019.
  * [7] Kevin Buchin, Maike Buchin, and Yusu Wang.  Exact algorithms for partial curve matching via the Fréchet distance.  In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 645–654, USA, January 2009. Society for Industrial and Applied Mathematics.
  * [8] Kevin Buchin, Tim Ophelders, and Bettina Speckmann.  SETH says: weak fréchet distance is faster, but only if it is continuous and in one dimension.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2887–2901, USA, January 2019. Society for Industrial and Applied Mathematics.
  * [9] Siu-Wing Cheng, Jiongxin Jin, and Antoine Vigneron.  Triangulation Refinement and Approximate Shortest Paths in Weighted Regions.  In Proceedings of the 2015 Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, pages 1626–1640. Society for Industrial and Applied Mathematics, December 2014.
  * [10] Kenneth L. Clarkson.  Approximation algorithms for shortest path motion planning.  In Proceedings of the nineteenth annual ACM Symposium on Theory of Computing, pages 56–65, New York, NY, USA, January 1987. Association for Computing Machinery.
  * [11] Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars.  Computational Geometry: Algorithms and Applications.  Springer, Berlin, Heidelberg, 2008.
  * [12] Sarita de Berg, Guillermo Esteban, Rodrigo I. Silveira, and Frank Staals.  Exact solutions to the Weighted Region Problem, February 2024.  arXiv:2402.12028 [cs].
  * [13] Jean-Lou de Carufel, Amin Gheibi, Anil Maheshwari, Jörg-Rüdiger Sack, and Christian Scheffer.  Similarity of polygonal curves in the presence of outliers.  Computational Geometry, 47(5):625–641, July 2014.
  * [14] Jean-Lou de Carufel, Carsten Grimm, Anil Maheshwari, Megan Owen, and Michiel Smid.  A note on the unsolvability of the weighted region shortest path problem.  Computational Geometry, 47(7):724–727, August 2014.
  * [15] Herbert Edelsbrunner.  Computing the extreme distances between two convex polygons.  Journal of Algorithms, 6(2):213–224, June 1985.
  * [16] Jeff Erickson.  Algorithms.  First edition, June 2019.
  * [17] Laxmi P. Gewali, Alex C. Meng, Joseph S. B. Mitchell, and Simeon Ntafos.  Path planning in 0/1/infinity weighted regions with applications.  In Proceedings of the Fourth Annual Symposium on Computational Geometry, pages 266–278, New York, NY, USA, January 1988. Association for Computing Machinery.
  * [18] Leonidas Guibas, John Hershberger, and Jack Snoeyink.  Compact interval trees: a data structure for convex hulls.  International Journal of Computational Geometry & Applications, 01(01):1–22, March 1991.
  * [19] David Kirkpatrick and Jack Snoeyink.  Computing common tangents without a separating line.  In Gerhard Goos, Juris Hartmanis, Jan Leeuwen, Selim G. Akl, Frank Dehne, Jörg-Rüdiger Sack, and Nicola Santoro, editors, Algorithms and Data Structures, volume 955, pages 183–193. Springer Berlin Heidelberg, Berlin, Heidelberg, 1995.  Series Title: Lecture Notes in Computer Science.
  * [20] Mark Lanthier, Anil Maheshwari, and Jörg-Rüdiger Sack.  Approximating weighted shortest paths on polyhedral surfaces.  In Proceedings of the Thirteenth Annual Symposium on Computational Geometry, pages 274–283, New York, NY, USA, August 1997. Association for Computing Machinery.
  * [21] Joseph S. B. Mitchell and Christos H. Papadimitriou.  The weighted region problem: finding shortest paths through a weighted planar subdivision.  Journal of the ACM, 38(1):18–73, January 1991.
  * [22] Giri Narasimhan and Michiel Smid.  Geometric Spanner Network.  Cambridge University Press, 2007.
  * [23] Zheng Sun and John H. Reif.  On finding approximate optimal paths in weighted regions.  Journal of Algorithms, 58(1):1–32, January 2006.
  * [24] Victor Andreevich Toponogov.  Differential Geometry of Curves and Surfaces: A Concise Guide.  Birkhauser.