The Spanning Ratio of the Directed Θ₆-Graph Is 5

Bose, Prosenjit; De Carufel, Jean-Lou; Stuart, John; Hill, Darryl

doi:10.4230/LIPIcs.SoCG.2026.20

The Spanning Ratio of the Directed $\Theta_{6}$ -Graph Is 5

Prosenjit Bose

School of Computer Science, Carleton University, Ottawa, Canada Jean-Lou De Carufel

School of Electrical Engineering and Computer Science, University of Ottawa, Canada John Stuart

School of Electrical Engineering and Computer Science, University of Ottawa, Canada Darryl Hill

School of Computer Science, Carleton University, Ottawa, Canada

Abstract

Given a finite set $P\subset\mathbb{R}^{2}$ , the directed Theta-6 graph, denoted $\vec{\Theta}_{6}(P)$ , is a well-studied geometric graph due to its close relationship with the Delaunay triangulation. The $\vec{\Theta}_{6}(P)$ -graph is defined as follows: the plane around each point $u\in P$ is partitioned into $6$ equiangular cones with apex $u$ , and in each cone, $u$ is joined to the point whose projection on the bisector of the cone is closest. Equivalently, the $\vec{\Theta}_{6}(P)$ -graph contains an edge from $u$ to $v$ exactly when the interior of $\nabla_{u}^{v}$ is disjoint from $P$ , where $\nabla_{u}^{v}$ is the unique equilateral triangle containing $u$ on a corner, $v$ on the opposite side, and whose sides are parallel to the cone boundaries. It was previously shown that the spanning ratio of the $\vec{\Theta}_{6}(P)$ -graph is between $4$ and $7$ in the worst case (Akitaya, Biniaz, and Bose Comput. Geom., 105-106:101881, 2022). We close this gap by showing a tight spanning ratio of 5. This is the first tight bound proven for the spanning ratio of any $\vec{\Theta}_{k}(P)$ -graph. Our lower bound models a long path by mapping it to a converging series. Our upper bound proof uses techniques novel to the area of spanners. We use linear programming to prove that among several candidate paths, there exists a path satisfying our bound.

Keywords and phrases:

Geometric Spanners, Theta Graphs, Directed Theta Graphs, Spanning Ratio, Computational Geometry

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Sparsification and spanners ; Theory of computation

\rightarrow

Computational geometry ; Theory of computation

\rightarrow

Shortest paths

Editors:

Hee-Kap Ahn, Michael Hoffmann, and Amir Nayyeri

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Studying the distance-preserving properties of particular families of graphs in the plane has been an active area of research for decades. This area has numerous applications, such as motion planning, or wireless routing. We will focus on geometric graphs where each vertex is a point in the plane, and each edge is weighted by the Euclidean distance between its endpoints. Given a geometric graph $G$ , the spanning ratio of a subgraph $H$ is a measure of how well distances of $G$ are preserved. In particular, a subgraph $H$ is called a $c$ -spanner of $G$ if for every edge $u v$ in $G$ , the shortest path in $H$ from $u$ to $v$ is at most $c$ times the length of the edge $u v$ in $G$ [15]. The smallest such $c$ is referred to as the spanning ratio of $H$ . Finding a tight bound on the spanning ratio of different geometric graphs is a fundamental problem in computational geometry. A particular graph of interest is the Delaunay triangulation. It has an edge $u v$ when there exists a disk with $u$ and $v$ on its boundary and no vertices in its interior. The spanning ratio of the Delaunay triangulation has been studied for nearly 40 years, and the first constant upper bound proven was $\frac{1+\sqrt{5}}{2}\pi\approx 5.083$ [12]. Currently, the spanning ratio of the Delaunay triangulation is only known to be between $1.593$ [21] and $1.998$ [20], and finding the exact value remains a major open problem [15]. The first plane geometric graph proven to have a constant spanning ratio is the $\square$ -Delaunay graph, whose empty region is a square [9]. The proof was then generalized to the $\triangle$ -Delaunay graph, whose empty region is an equilateral triangle [10].

Delaunay triangulations have many desirable properties. A Delaunay triangulation is a plane graph, meaning that it contains roughly $3|V|$ undirected edges, therefore the average vertex degree is approximately $6$ . However, it is possible for a vertex to have arbitrarily large degree. In many applications, such as signal transmission, such a large degree may be problematic. Instead, we focus on a closely-related geometric graph with bounded outdegree of $6$ .

Given a finite set $P\subset\mathbb{R}^{2}$ and integer $k>1$ , we can construct a geometric graph on $P$ with at most $k$ outgoing edges per vertex as follows. For each vertex $u\in P$ , partition the plane into $k$ equiangular cones about $u$ . Then, add an edge from $u$ to the nearest vertex in each cone about $u$ . Repeat this process for each vertex of $P$ . If nearest is measured by the Euclidean distance, then the resulting graph is known as a Yao- $k$ graph, first studied by Yao [22]. The directed Theta- $k$ graph, denoted $\vec{\Theta}_{k}$ , is defined similarly, except that nearest is measured using a distance function whose unit disk is a regular $k$ -gon. In particular, the $\vec{\Theta}_{k}$ -graph contains an edge from $u$ to $v$ in cone $C$ when the orthogonal projection of $u v$ onto the cone bisector is minimal among all vertices $v$ in cone $C$ . We refer to the undirected version as the $\Theta_{k}$ -graph. Since being introduced by Clarkson [11] and Keil and Gutwin [13], $\Theta_{k}$ -graphs have been studied extensively. For $k\geq 4$ , the $\Theta_{k}$ -graph is known to be a spanner of the complete graph [2, 4, 6, 11, 13, 17]. On the other hand, the $\vec{\Theta}_{k}$ -graph is known to be a constant spanner for $k\geq 6$ [1, 6, 17] and also for $k=4$ [4]. Despite extensive research, tight bounds on the spanning ratio are only known for the $\Theta_{4k+2}$ -graph when $k\geq 1$ . In general, results claiming tight bounds on the spanning ratio of any geometric graph are rare. To the best of our knowledge, the only other geometric graphs with known tight spanning ratios are the three generalized Delaunay graphs whose empty regions are either a triangle, square, or hexagon. See Table 1.

Table 1: Other geometric graphs with known tight spanning ratios.

Reference	Graph	Spanning Ratio	Notes
[6]	$\Theta_{4k+2}$ ( $k\geq 1$ )	$1+2\sin(\theta/2)$	Also for constrained version [8]
[10]	$\triangle$ -Delaunay	$2$	Also for affine transformations [18, 14]
[3]	$\square$ -Delaunay	$\sqrt{4+2\sqrt{2}}\approx 2.613$	Also for affine transformations [7, 19]
[16]	-Delaunay	$2$

The $\vec{\Theta}_{6}$ -graph has a special symmetry. For two points $u,v\in P$ , we can define $\nabla_{u}^{v}$ to be the unique equilateral triangle whose sides have slopes $-\sqrt{3}$ , $0$ , and $\sqrt{3}$ and $u$ is on a corner and $v$ is on the opposite side. Then the $\vec{\Theta}_{6}$ -graph contains an edge from $u$ to $v$ exactly when the interior of $\nabla_{u}^{v}$ contains no vertices of $P$ . Readers familiar with Delaunay triangulations may notice that the $\vec{\Theta}_{6}$ -graph is essentially two rotated copies of a $\triangle$ -Delaunay graph. The $\triangle$ -Delaunay graph, often referred to as the TD-Delaunay graph, has a spanning ratio of $2$ in the worst case, hence the Theta- $6$ graph inherits this upper bound. On the other hand, the $\vec{\Theta}_{6}$ -graph does not preserve distances nearly as well as its undirected counterpart. The first bounds on the spanning ratio of the $\vec{\Theta}_{6}$ -graph were given by Akitaya, Biniaz, and Bose [1]. For any $\epsilon>0$ , they construct a $\vec{\Theta}_{6}$ -graph whose spanning ratio is at least $4-\epsilon$ . Then, they show that constructing a path in an arbitrary $\vec{\Theta}_{6}$ -graph is not as straightforward as selecting the outgoing edge in the cone containing the destination. This technique is known as greedy routing, and it produces efficient paths in $\vec{\Theta}_{k}$ -graphs only when $k\geq 7$ [17]. Greedy routing in $\vec{\Theta}_{6}$ -graphs can lead to a spiraling path of unbounded length. Instead, the authors of [1] give an upper bound of $7$ for the spanning ratio of $\vec{\Theta}_{6}$ -graphs using the following technique. Given an edge from $a$ to $b$ , they show that the greedy path from $b$ to $a$ has length at most $6$ times the length of the edge from $a$ to $b$ . Then, for any two vertices $s, t$ , it suffices to find an intermediate vertex $x$ such that there are short paths from $s$ to $x$ and $t$ to $x$ . Indeed, a path from $s$ to $t$ can be formed by concatenating the path from $s$ to $x$ with the greedy paths corresponding to each edge on the path from $t$ to $x$ . The authors leave it as an open problem to close the gap between $4$ and $7$ . As the title of our paper suggests, we close this gap by showing that the $\vec{\Theta}_{6}$ -graph has a tight spanning ratio of $5$ .

Our proof uses elements from [1] along with several novel techniques in the area of spanners. Most notably, we use linear programming to prove the existence of a short path. At a high level, our proof is an induction on the distance between points, and it proceeds as follows. We define a special region $R$ between $s$ and $t$ , and show that if there exists a vertex $x\in R$ , then induction provides two paths, from $s$ to $x$ and from $x$ to $t$ , which can be concatenated to form a sufficiently short path from $s$ to $t$ . Then, for the rest of the proof, we assume that no vertices are in the interior of $R$ . Importantly, we are able to show that any edge $u v$ on the greedy path that crosses $R$ must pay a “toll”. More precisely, $v$ is guaranteed to be at least twice as close to $t$ as $u$ . We leverage this property by applying induction after a candidate path crosses $R$ . The difficulty is that there are multiple candidate paths, and determining which path is sufficiently short is non-trivial. Our solution is to assume that there is no sufficiently short candidate path. This allows us to prove inequalities corresponding to each candidate path, then we can use linear programming to show that the system is infeasible. In essence, assuming that there is no short path leads to a contradiction.

2 Preliminaries

The geometric graphs we study are weighted, directed graphs whose vertex sets contain points in the plane. We denote the directed edge from vertex $u$ to vertex $v$ by $u v$ , and with a slight abuse of notation, when $p,q\in\mathbb{R}^{2}$ , we denote the segment from $p$ to $q$ as $p q$ . In general, for an edge $u v$ and a norm $\|\cdot\|$ , the value $\|uv\|$ is exactly the factor by which the unit disk of $\|\cdot\|$ must be scaled such that the unique translate with $u$ in the center has $v$ on the boundary. For example, $\|\cdot\|_{2}$ refers to the Euclidean norm whose unit disk is a circle with radius $1$ . We also let $\|uv\|_{x}$ (resp. $\|uv\|_{y}$ ) denote the absolute difference in $x$ -coordinate (resp. $y$ -coordinate) from $u$ and $v$ . The Manhattan norm, $\|uv\|_{1}:=\|uv\|_{x}+\|uv\|_{y}$ , has a tipped square with side length $\sqrt{2}$ as its unit disk. For an edge $u v$ in a geometric graph, we define its weight to be $\|uv\|_{2}$ , the usual distance from $u$ to $v$ . Let $\|\cdot\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf% 2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf% 2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}% {\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$ denote the hexagonal norm whose unit disk is a regular hexagon with east and west vertices equal to $(1,0)$ and $(-1,0)$ , respectively. On the other hand, let $\|\cdot\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf% 2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf% 2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}% {\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$ denote the tipped hexagonal norm whose unit disk is a tipped regular hexagon with north and south vertices equal to $(0,\frac{2}{\sqrt{3}})$ and $(0,\frac{-2}{\sqrt{3}})$ , respectively. See Figure 1. Notice that we always have $\|uv\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}\leq\|uv\|_{% 2}\leq\|uv\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$ , and equality holds exactly when $u v$ has slope $-\sqrt{3}$ , $0$ , or $\sqrt{3}$ .

Figure 1: Left: The dotted circle represents the unit disk in the standard Euclidean norm (

\|\cdot\|_{2}

). The shaded inner hexagon is the unit disk in the

\|\cdot\|_{\mathchoice{\includegraphics[height=5.42496pt]{DirTh6-2-page-97.pdf% 2svg.svg}}{\vbox{\hbox{\includegraphics[height=5.42496pt]{DirTh6-2-page-97.pdf% 2svg.svg}}}}{\includegraphics[height=4.06871pt]{DirTh6-2-page-97.pdf2svg.svg}}% {\includegraphics[height=2.71248pt]{DirTh6-2-page-97.pdf2svg.svg}}}

-norm. The outer tipped hexagon is the unit disk in the

\|\cdot\|_{\mathchoice{\includegraphics[height=5.42496pt]{DirTh6-2-page-98.pdf% 2svg.svg}}{\vbox{\hbox{\includegraphics[height=5.42496pt]{DirTh6-2-page-98.pdf% 2svg.svg}}}}{\includegraphics[height=4.06871pt]{DirTh6-2-page-98.pdf2svg.svg}}% {\includegraphics[height=2.71248pt]{DirTh6-2-page-98.pdf2svg.svg}}}

-norm. Right: The six cones about

p

are labeled in counterclockwise order from

C_{p}^{0}

below

p

. The dotted green bisector is

B_{p}^{0}

and the red ray is

R_{p}^{0}

. The empty shaded triangle in

C_{p}^{1}

is

\nabla_{p}^{q}

. Each shaded region is empty.

In a geometric graph $G$ , we define the length of a path to be the sum of the weights of its edges. For any norm $\|\cdot\|$ and path $\mathcal{P}$ , we define $\|\mathcal{P}\|:=\sum_{uv\text{ on }\mathcal{P}}\|uv\|$ . If $v$ is a vertex on a path $\mathcal{P}$ , then we define the truncated path $\mathcal{P}_{v}$ as the subpath of $\mathcal{P}$ which ends at $v$ . For two vertices $u, v$ in a geometric graph $G$ , we let $d_{G}(u,v)$ denote the length of the shortest path in $G$ from $u$ to $v$ . Recall that all edges are weighted by the Euclidean norm. Then for a constant $c\geq 1$ , $G$ is said to be a $c$ -spanner if for all points $u, v$ in $G$ , we have $d_{G}(u,v)\leq c\|uv\|_{2}$ . The spanning ratio of $G$ is the least $c$ for which $G$ is a $c$ -spanner. The spanning ratio of a class of graphs $\mathcal{G}$ is the least $c$ for which all graphs in $\mathcal{G}$ are $c$ -spanners.

For any point $p$ , consider the three lines passing through $p$ with slopes $-\sqrt{3}$ , $0$ , and $\sqrt{3}$ . These lines partition the plane into six cones about $p$ , which we label counter-clockwise by $C_{p}^{i}$ for $i\in\mathbb{Z}_{6}$ starting with $C_{p}^{0}$ directly below $p$ . Here, $\mathbb{Z}_{6}$ refers to the integers modulo $6$ . See Figure 1. For each cone $C_{p}^{i}$ , we denote its bisector by $B_{p}^{i}$ . Throughout this paper, we adopt the convention that cones are closed sets, otherwise we write $\text{int}(R)$ to denote the interior of region $R$ . For $i\in\mathbb{Z}_{6}$ , we define the ray $R_{p}^{i}:=C_{p}^{i}\cap C_{p}^{i+1}$ . For points $p,q\in\mathbb{R}^{2}$ with $q\in C_{p}^{i}$ , we let $\nabla_{p}^{q}$ denote the triangular region $\{r\in C_{p}^{i}\mid\|pr\|_{\mathchoice{\includegraphics[height=6.02777pt]{% DirTh6-2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{% DirTh6-2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-% page-97.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2% svg.svg}}}\leq\|pq\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-% page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-% page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}% }}\}$ . For any equilateral triangle $T$ , we let $\|T\|$ denote the side length of $T$ . Notice that $\|\nabla_{p}^{q}\|=\|pq\|_{\mathchoice{\includegraphics[height=6.02777pt]{% DirTh6-2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{% DirTh6-2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-% page-97.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2% svg.svg}}}$ . For any finite point set $P\subset\mathbb{R}^{2}$ , we make the general position assumption that no two vertices lie on a line with slope $-\sqrt{3}$ , $0$ , or $\sqrt{3}$ . The directed Theta-6 graph of $P$ , denoted $\vec{\Theta}_{6}(P)$ , contains an edge from vertex $u$ to vertex $v$ exactly when $\text{int}(\nabla_{u}^{v})\cap P=\emptyset$ . Intuitively, a vertex has an outgoing edge to the nearest vertex in each of its six cones, measured using the $\|\cdot\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf% 2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf% 2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}% {\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$ -norm. For any vertices $u,v\in P$ , we let $\pi(u,v)$ denote the greedy path from $u$ to $v$ . In particular, every edge $a b$ of $\pi(u,v)$ satisfies $b\in C_{a}^{i}\iff v\in C_{a}^{i}$ . If $w$ is a vertex along the path $\pi(u,v)$ , then the subpath terminating at $w$ is denoted by $\pi(u,v)_{w}$ . Note that if $w\neq v$ , then $\pi(u,v)_{w}$ is not necessarily the same as $\pi(u,w)$ .

3 Lower Bound

Lemma 1.

For any $\epsilon>0$ , there exists a $\vec{\Theta}_{6}$ -graph with spanning ratio at least $5-\epsilon$ .

Proof.

Let $\epsilon>0$ be arbitrarily small. We will construct a $\vec{\Theta}_{6}$ -graph with spanning ratio at least $5-\epsilon$ , shown in Figure 2.

Figure 2: Graph construction achieving a spanning ratio lower bound of

5-\epsilon

. The shortest path from

s

to

t

is the greedy path

s,a,b,c,p^{0},q^{0},p^{1},q^{1},...,,q^{k-1},p^{k},t

. Top Left: The colour coding for edges based on direction.

For the following construction, set $0<\delta<\frac{\epsilon}{72}$ . Define the points $t:=(0,0)$ , $s:=(-1,0)+\delta(1,-1),a:=(-\frac{1}{2},\frac{\sqrt{3}}{2})+\delta(1,-2),b:=(% \frac{1}{2},\frac{\sqrt{3}}{2})+\delta(-2,-3),c:=(1,0)+\delta(-6,1)$ . Next, let $p^{0}$ be the unique point such that $tp^{0}$ has slope $-\delta$ and $p^{0}c$ has slope $\sqrt{3}-\delta$ . Next, let $q^{0}$ be on segment $c t$ such that $p^{0}q^{0}$ has slope $\delta-\sqrt{3}$ . For $i>0$ , let $q^{i}$ be on $c t$ such that $\frac{\|q^{i-1}q^{i}\|_{2}}{\|tq^{i}\|_{2}}=\frac{\|q^{0}c\|_{2}}{\|tc\|_{2}}$ . For $i>0$ , also define $p^{i}$ to be on $tp^{0}$ such that $p^{i}q^{i}$ has slope $\delta-\sqrt{3}$ . We let $k$ be the least integer such that $p_{k}$ has $x$ -coordinate less than $\delta$ . We have constructed the point set $P:=\{t,s,a,b,c\}\cup\{p^{0},p^{1},...,p^{k}\}\cup\{q^{0},q^{1},...,q^{k-1}\}$ . In $\vec{\Theta}_{6}(P)$ , the shortest path from $s$ to $t$ is $s,a,b,c,p^{0},q^{0},p^{1},q^{1},...q^{k-1},p^{k},t$ since from the perspective of any vertex on the path, all subsequent vertices lie in the same cone. Now we will lower bound the length of this path. First, we have

$\displaystyle 1$	$\displaystyle=\\|(-1,0)(-\frac{1}{2},\frac{\sqrt{3}}{2})\\|_{2}$	since $\sqrt{\left(\frac{1}{2}\right)^{2}+\left(\frac{\sqrt{3}}{2}\right)^{2}}=1$ ,
	$\displaystyle\leq\\|(-1,0)s\\|_{2}+\\|sa\\|_{2}+\\|a(-\frac{1}{2},\frac{\sqrt{3}}{2% })\\|_{2}$	by triangle inequality,
	$\displaystyle\leq\\|(-1,0)s\\|_{1}+\\|sa\\|_{2}+\\|a(-\frac{1}{2},\frac{\sqrt{3}}{2% })\\|_{1}$	since $\\|\cdot\\|_{2}\leq\\|\cdot\\|_{1}$ ,
	$\displaystyle=2\delta+\\|sa\\|_{2}+3\delta$	by definition.	(1)

which implies $\|sa\|_{2}\geq 1-5\delta$ . Using the same technique, we can obtain the following bounds: $\|ab\|_{2}\geq 1-8\delta$ and $\|bc\|_{2}\geq 1-12\delta$ . Next, let $r$ be the unique point such that $p^{k}r$ has slope $\sqrt{3}-\delta$ and $rp^{0}$ has slope $\delta-\sqrt{3}$ . Then by unfolding, notice that the path $p^{0},q^{0},p^{1},q^{1},...,p^{k-1},q^{k-1},p^{k}$ has length $\|p^{0}r\|_{2}+\|rp^{k}\|_{2}$ . See Figure 2. By the triangle inequality, we have $\|p^{0}(1,0)\|_{1}\leq\|p^{0}c\|_{x}+\|p^{0}c\|_{y}+\|c(1,0)\|_{1}\leq 2\delta% +2\delta+7\delta=11\delta$ and $\|tp^{k}\|_{1}=\|tp^{k}\|_{x}+\|tp^{k}\|_{y}\leq\delta+\delta=2\delta$ . Next, we claim that $r$ approaches $(\frac{1}{2},\frac{\sqrt{3}}{2})$ as $\delta\to 0$ .

Claim 2.

We have $\|r(\frac{1}{2},\frac{\sqrt{3}}{2})\|_{2}\leq 17\delta$ . See full version for details [5].

Now we can apply the same technique used to prove inequality (3) to obtain $\|p^{0}r\|_{2}\geq 1-28\delta$ and $\|rp^{k}\|_{2}\geq 1-19\delta$ . Therefore the total length of the path is at least

	$\displaystyle d_{\vec{\Theta}_{6}(P)}(s,t)$	$\displaystyle=\\|sa\\|_{2}+\\|ab\\|_{2}+\\|bc\\|_{2}+\\|cp^{0}\\|_{2}+\left(\sum_{i=0}% ^{k-1}\\|p^{i}q^{i}\\|_{2}\right)+\\|q^{k-1}p^{k}\\|_{2}+\\|p_{k}t\\|_{2}$
		$\displaystyle\geq(1-5\delta)+(1-8\delta)+(1-12\delta)+(1-28\delta)+(1-19\delta)$
		$\displaystyle=5-72\delta>5-\epsilon.$

Then since $\|st\|_{2}\leq 1$ , the spanning ratio of $\vec{\Theta}_{6}(P)$ is at least $5-\epsilon$ . $\hfill\blacktriangleleft$

4 Upper Bound

The goal of this section is to prove Theorem 3.

Theorem 3.

For any point set $P\subset\mathbb{R}^{2}$ in general position, we have $d_{\vec{\Theta}_{6}(P)}(s,t)\leq 5\|st\|_{\mathchoice{\includegraphics[height=% 6.02777pt]{DirTh6-2-page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=% 6.02777pt]{DirTh6-2-page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]% {DirTh6-2-page-98.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-% page-98.pdf2svg.svg}}}\leq 5\|st\|_{2}$ $\forall s,t\in P$ .

Let $P\subset\mathbb{R}^{2}$ be a point set in general position, and let $G:=\vec{\Theta}_{6}(P)$ . Recall that the $\|\cdot\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf% 2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf% 2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}% {\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$ -norm is used to define $G$ , however Theorem 3 is expressed in terms of the $\|\cdot\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf% 2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf% 2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}% {\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$ -norm. The following lemma describes the exact relationship between $\|\cdot\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf% 2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf% 2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}% {\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$ and $\|\cdot\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf% 2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf% 2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}% {\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$ .

Lemma 4.

Let $u\in\mathbb{R}^{2}$ , $i\in\mathbb{Z}_{6}$ , and $v\in C_{u}^{i}$ . Then

\|uv\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}=\|uv\|_{% \mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.svg}}}% }{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}+\frac{1}{2}% \min(\|C_{u}^{i}\cap C_{v}^{i-2}\|,\|C_{u}^{i}\cap C_{v}^{i+2}\|).

Proof.

Suppose without loss of generality that $i=0$ and $v$ is to the right of the bisector $B_{u}^{0}$ . See Figure 3. Then $\|C_{u}^{0}\cap C_{v}^{2}\|\leq\|C_{u}^{0}\cap C_{v}^{4}\|$ . Let $a$ be the orthogonal projection of $v$ on $R_{u}^{0}$ . Also let $b$ be the intersection of $R_{u}^{0}$ with a horizontal line through $v$ . Then

\|uv\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}+\frac{1}{2}% \|C_{u}^{0}\cap C_{v}^{2}\|=\|ua\|_{2}+\|ab\|_{2}=\|ub\|_{2}=\|uv\|_{% \mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}}% }{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}.

The other cases follow by symmetry.

Figure 3: Lemma 4 with

v\in C_{u}^{0}

. The dotted vertical ray is the bisector

B_{u}^{0}

. The horizontal green dashed segment represents all points

p\in C_{u}^{0}

such that

\|up\|_{\mathchoice{\includegraphics[height=5.42496pt]{DirTh6-2-page-97.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=5.42496pt]{DirTh6-2-page-97.pdf2% svg.svg}}}}{\includegraphics[height=4.06871pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=2.71248pt]{DirTh6-2-page-97.pdf2svg.svg}}}=\|uv\|_{% \mathchoice{\includegraphics[height=5.42496pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \vbox{\hbox{\includegraphics[height=5.42496pt]{DirTh6-2-page-97.pdf2svg.svg}}}% }{\includegraphics[height=4.06871pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=2.71248pt]{DirTh6-2-page-97.pdf2svg.svg}}}

. The red dashed segments represent all points

p\in C_{u}^{0}

such that

\|up\|_{\mathchoice{\includegraphics[height=5.42496pt]{DirTh6-2-page-98.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=5.42496pt]{DirTh6-2-page-98.pdf2% svg.svg}}}}{\includegraphics[height=4.06871pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=2.71248pt]{DirTh6-2-page-98.pdf2svg.svg}}}=\|uv\|_{% \mathchoice{\includegraphics[height=5.42496pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \vbox{\hbox{\includegraphics[height=5.42496pt]{DirTh6-2-page-98.pdf2svg.svg}}}% }{\includegraphics[height=4.06871pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=2.71248pt]{DirTh6-2-page-98.pdf2svg.svg}}}

.

$\hfill\blacktriangleleft$ The next lemma finds use in proving Theorem 3

Lemma 5.

Let $u,v,t\in P$ and $i\in\mathbb{Z}_{6}$ . Suppose $u,v\in C_{t}^{i}\cup C_{t}^{i+1}$ between $B_{t}^{i}$ and $B_{t}^{i+1}$ . Then if $v\in C_{u}^{i+3}\cup C_{u}^{i+4}$ , we have $\|uv\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}\leq 2(\|ut% \|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.% svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.% svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}-\|vt\|_{% \mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.svg}}}% }{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}})$ .

Proof.

Without loss of generality, suppose $i=0$ . If $v\in C_{u}^{3}$ , then define $p:=R_{u}^{2}\cap R_{v}^{1}$ , otherwise, if $v\in C_{u}^{4}$ , then define $p:=R_{u}^{4}\cap R_{v}^{5}$ . Let $v^{\prime}$ and $p^{\prime}$ be the orthogonal projections of $v$ and $p$ on $R_{u}^{3}$ . See Figure 4. Then

\|uv\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}=\|up\|_{2}=% 2\|up^{\prime}\|_{2}\leq 2\|uv^{\prime}\|_{2}=2(\|ut\|_{\mathchoice{% \includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.svg}}{\vbox{\hbox{% \includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.svg}}}}{% \includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}-\|vt\|_{% \mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.svg}}}% }{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}).\

Figure 4: For the proof of Lemma 5, we assume

i=0

and show the case when

v\in C_{u}^{4}

on the left and

v\in C_{u}^{3}

on the right.

$\hfill\blacktriangleleft$

We prove Theorem 3 by induction on the hexagonal distance $\|\cdot\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf% 2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf% 2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}% {\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$ between vertices. For the base case, consider the closest pair of vertices $s,t\in P$ (i.e. $\|st\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$ is minimal). Minimality implies $\text{int}(\nabla_{s}^{t})$ must not contain any vertices of $P$ . Therefore there must be an edge from $s$ to $t$ , yielding $d_{G}(s,t)=\|st\|_{2}\leq 5\|st\|_{\mathchoice{\includegraphics[height=6.02777% pt]{DirTh6-2-page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777% pt]{DirTh6-2-page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6% -2-page-98.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.% pdf2svg.svg}}}$ .

For the remainder of the proof, fix $s,t\in P$ and suppose that for any vertices $u,v\in P$ , if $\|uv\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}<\|st\|_{% \mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}}% }{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$ , then $d_{G}(u,v)\leq 5\|uv\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-% 2-page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-% 2-page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$ . We will assume $\|st\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}=1$ since our argument holds when scaling the point set. Without loss of generality, suppose $s\in C_{t}^{0}$ , with $s$ being to the right of $B_{t}^{0}$ . Define the triangle $T=C_{t}^{0}\cap C_{s}^{2}$ , and denote its side length by $y_{0}:=\|T\|$ . Notice that $y_{0}$ describes the hex distance from $s$ to the nearest boundary, and by Lemma 4, we obtain $5\|st\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}=5-2.5y_{0}$ . Suppose towards a contradiction that $5\|st\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}<d_{G}(s,t)$ . Our approach is to analyse paths from $s$ to $t$ , which will allow us to prove inequalities based on our faulty assumption. These inequalities will form a linear system, then linear programming will help us show that the system is infeasible. The first step in our proof is to establish an empty region which we refer to as $R$ .

Definition 6 (Empty Region $R$ ).

Consider the points $p:=B_{s}^{3}\cap B_{t}^{1}$ and $q=B_{s}^{4}\cap B_{t}^{0}$ . See Figure 5. Let $Q$ denote the parallelogram with vertices $s, q, t, p$ , and define the region $R:=Q\cup\nabla_{s}^{p}\cup\nabla_{s}^{q}$ .

Figure 5: The red triangle is

\nabla_{s}^{p}

, the orange triangle is

\nabla_{s}^{q}

, and the shaded parallelogram is

Q

. Their union is

R

, whose interior can be assumed to not contain any vertices by Lemma 7. Furthermore, there exists a vertex

y\in C_{t}^{1}

close to the horizontal line through

t

. The triangle

T

has side-length

y_{0}

and the triangle

C_{t}^{1}\cap C_{y}^{3}

has side-length

y_{1}

.

Let $y$ be the vertex such that $s y$ is the edge in $C_{s}^{3}$ and consider the quantity $y_{1}:=1-\|\nabla_{s}^{y}\|$ describing the hexagonal distance $\|\cdot\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf% 2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf% 2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}% {\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$ from $y$ to the horizontal line through $t$ . In addition to proving that $R$ is empty, the following lemma proves that $y_{0}$ and $y_{1}$ cannot both be large. Geometrically, $s$ must be near $R_{t}^{0}$ and $y$ must be near $R_{t}^{1}$ . See Figure 5.

Lemma 7.

If $d_{G}(s,t)>5\|st\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-% page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-% page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$ , then $\text{int}(R)$ does not contain any vertices of $P$ . Furthermore, $y\in C_{t}^{1}$ and

\displaystyle 2.5y_{0}+3.5y_{1}<1

(2)

Proof.

See Figure 6. If there exists a vertex $w\in Q$ with $w\notin\{s,t\}$ , then $\|wt\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}<1$ . We obtain

$\displaystyle d_{G}(s,t)$	$\displaystyle\leq d_{G}(s,w)+d_{G}(w,t)$	by triangle inequality,
	$\displaystyle\leq 5\\|sw\\|_{\mathchoice{\includegraphics[height=6.02777pt]{% DirTh6-2-page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{% DirTh6-2-page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-% page-98.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2% svg.svg}}}+5\\|wt\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-% page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-% page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$	by induction,
	$\displaystyle=5\\|st\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2% -page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2% -page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$	by $\\|\cdot\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf% 2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf% 2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}% {\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$ collinearity.

Figure 6: If there is a vertex

w

in the dark shaded parallelogram, denoted

Q

, then induction yields paths from

s

to

w

and from

w

to

t

. If there is an edge

s y

in the light shaded triangle

\nabla_{s}^{p}\setminus Q

, then induction yields a path from

y

to

t

. Similarly, if there is an edge

s x

in the light shaded triangle

\nabla_{s}^{q}\setminus Q

, then induction yields a path from

x

to

t

.

Therefore we may assume parallelogram $Q$ contains no vertices. Next we will rule out the possibility of $y\in C_{t}^{5}\cup C_{t}^{0}$ . If $y\in C_{t}^{5}$ , then we have

$\displaystyle d_{G}(s,t)$	$\displaystyle\leq\\|sy\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6% -2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6% -2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97% .pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg% }}}+d_{G}(y,t)$	by triangle inequality,
	$\displaystyle\leq 1+5y_{0}$	by induction as $\\|yt\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}\leq\\|yt\\|_{% \mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}}% }{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}=\\|\nabla_{t% }^{y}\\|\leq\\|T\\|$
	$\displaystyle<5\\|st\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2% -page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2% -page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$	since $y_{0}\leq 0.5$ and $5-2.5y_{0}=5\\|st\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-% page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-% page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$ .

On the other hand if $y\in C_{t}^{0}$ or $y\in C_{t}^{1}$ below $B_{t}^{1}$ , then we use Lemma 5 to obtain $\|sy\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}\leq 2(\|st% \|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.% svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.% svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}-\|yt\|_{% \mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.svg}}}% }{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}})$ . Indeed, if $s y$ crosses $B_{t}^{0}$ , then let $z:=sy\cap B_{t}^{0}$ and apply Lemma 5 to both $s z$ and $z y$ . We obtain

$\displaystyle d_{G}(s,t)$	$\displaystyle\leq\\|sy\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6% -2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6% -2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97% .pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg% }}}+d_{G}(y,t)$	by triangle inequality,
	$\displaystyle\leq 2(\\|st\\|_{\mathchoice{\includegraphics[height=6.02777pt]{% DirTh6-2-page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{% DirTh6-2-page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-% page-98.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2% svg.svg}}}-\\|yt\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-% page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-% page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}% }})+5\\|yt\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$	by Lemma 5 and induction,
	$\displaystyle=2\\|st\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2% -page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2% -page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}% }}+3\\|yt\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$
	$\displaystyle<5\\|st\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2% -page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2% -page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$	since $\\|yt\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}<\\|st\\|_{% \mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.svg}}}% }{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$ .

Therefore we may assume $y\in C_{t}^{1}$ above the bisector $B_{t}^{1}$ . We have $\|yt\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}\leq\|C_{t}^% {1}\cap C_{s}^{3}\|=1-y_{0}$ . Recall that $y_{1}:=1-\|\nabla_{s}^{y}\|$ , and notice that we also have $y_{1}=\|C_{t}^{1}\cap C_{y}^{3}\|$ . By Lemma 4, $\|yt\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}=\|yt\|_{% \mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}}% }{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}-\frac{1}{2}% y_{1}$ . This gives us

$\displaystyle 5-2.5y_{0}$	$\displaystyle<d_{G}(s,t)$	by assumption,
	$\displaystyle\leq\\|sy\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6% -2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6% -2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97% .pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg% }}}+d_{G}(y,t)$	by triangle inequality,
	$\displaystyle\leq(1-y_{1})+(5(1-y_{0})-2.5y_{1})$	by $\\|\nabla_{s}^{y}\\|=\\|sy\\|_{\mathchoice{\includegraphics[height=6.02777pt]{% DirTh6-2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{% DirTh6-2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-% page-97.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2% svg.svg}}}$ and induction.	(3)

By re-arranging inequality (3), we obtain $2.5y_{0}+3.5y_{1}<1$ , proving (2). Notice that $2y_{0}+3(1-\|sp\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-% page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-% page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}% }})=1$ by symmetry of isosceles triangles. We have

\displaystyle y_{1}<\frac{1-2.5y_{0}}{3.5}<\frac{1-2y_{0}}{3}=1-\|sp\|_{% \mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}}% }{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}},

which implies that the region $\text{int}(\nabla_{s}^{p})$ contains no vertices. Indeed, if there were a point $u\in\text{int}(\nabla_{s}^{p})$ , then $1-y_{1}=\|sy\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-9% 7.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-9% 7.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}\leq\|% su\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg.% svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg.% svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}\leq\|sp\|_{% \mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}}% }{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$ . Thus far we have shown that $Q$ and $\nabla_{s}^{p}$ do not contain vertices in their interior, hence it remains to argue that $\text{int}(\nabla_{s}^{q})$ is also empty. Towards a contradiction, assume there is a vertex $x\in\text{int}(\nabla_{s}^{q})$ . If $x$ is to the right of the bisector $B_{t}^{0}$ , then we have

$\displaystyle d_{G}(s,t)$	$\displaystyle\leq\\|sx\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6% -2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6% -2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97% .pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg% }}}+d_{G}(x,t)$	by triangle inequality,
	$\displaystyle\leq 2(\\|st\\|_{\mathchoice{\includegraphics[height=6.02777pt]{% DirTh6-2-page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{% DirTh6-2-page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-% page-98.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2% svg.svg}}}-\\|xt\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-% page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-% page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}% }})+5\\|xt\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$	by Lemma 5 and induction,
	$\displaystyle=2\\|st\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2% -page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2% -page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}% }}+3\\|xt\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$
	$\displaystyle<5\\|st\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2% -page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2% -page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$	since $\\|xt\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}<\\|st\\|_{% \mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.svg}}}% }{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$ .

On the other hand if $x$ is to the left of the bisector $B_{t}^{0}$ , then let $q^{0}:=R_{q}^{5}\cap R_{s}^{4}$ and $q^{1}:=R_{q}^{0}\cap R_{s}^{4}$ . Notice that $\|sq^{0}\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}=2\|sq% ^{1}\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$ . We have

$\displaystyle d_{G}(s,t)$	$\displaystyle\leq\\|sx\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6% -2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6% -2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97% .pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg% }}}+d_{G}(x,t)$	by triangle inequality,
	$\displaystyle\leq\\|sq^{0}\\|_{\mathchoice{\includegraphics[height=6.02777pt]{% DirTh6-2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{% DirTh6-2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-% page-97.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2% svg.svg}}}+5\\|xt\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-% page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-% page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$	by induction,
	$\displaystyle\leq 2\\|sq^{1}\\|_{\mathchoice{\includegraphics[height=6.02777pt]{% DirTh6-2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{% DirTh6-2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-% page-97.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2% svg.svg}}}+5\\|q^{0}t\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-% 2-page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-% 2-page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$	since $\\|xt\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}\leq\\|q^{0}t% \\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.% svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.% svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$ ,
	$\displaystyle=2(2(\\|st\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh% 6-2-page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh% 6-2-page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-9% 8.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.% svg}}}-\\|q^{1}t\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-% page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-% page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}% }}))+5\\|q^{1}t\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page% -98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page% -98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2% svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$	by Lemma 5 and $\\|q^{0}t\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}=\\|q^{% 1}t\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg% .svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg% .svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$ ,
	$\displaystyle=4\\|st\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2% -page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2% -page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}% }}+\\|q^{1}t\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98% .pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98% .pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$
	$\displaystyle\leq 5\\|st\\|_{\mathchoice{\includegraphics[height=6.02777pt]{% DirTh6-2-page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{% DirTh6-2-page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-% page-98.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2% svg.svg}}}$	since $\\|q^{1}t\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}\leq\\|% st\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.% svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.% svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$ .

Therefore the region $\text{int}(\nabla_{s}^{q})$ contains no vertices. This completes the proof. $\hfill\blacktriangleleft$

Now that we have established an empty region $R$ and the position of $y$ , we would like to analyse the greedy path from $y$ to $t$ . Recall that for any vertices $u,v\in P$ , the greedy path from $u$ to $v$ is denoted $\pi(u,v)$ . Every edge $a b$ of $\pi(u,v)$ satisfies $b\in C_{a}^{i}\iff v\in C_{a}^{i}$ . Intuitively, the greedy path simply follows the edge in the direction of the destination. In [1] the authors show that for every edge $u v$ of $\pi(s,t)$ , we have $\|ut\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}>\|vt\|_{% \mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}}% }{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$ . However, this does not guarantee that the greedy path is an efficient path to $t$ . The main reason is that $\pi(s,t)$ may spiral around $t$ arbitrarily many times while making negligible progress. The authors of [1] show how to avoid a spiraling greedy path by assuming there is an edge from $t$ to $s$ and using the empty triangle $\nabla_{t}^{s}$ as an obstruction. This is done in Lemmas 2, 3 and 4 from [1], which we restate here using our notation.

Lemma 8 (Lemma 2 in [1]).

If edge $u v$ is on $\pi(u,t)$ and $u\in C_{t}^{i}$ , then $v\in C_{t}^{i-1}\cup C_{t}^{i}\cup C_{t}^{i+1}$ .

Lemma 9 (Lemma 3 in [1]).

Let $s,t\in P$ and assume $t s$ is an edge of $\vec{\Theta}_{6}(P)$ . Assume the vertices $a, b, c$ appear in this order in $\pi(s,t)$ , not necessarily distinct or consecutive. Then if $a$ and $c$ are both in the same cone $C_{t}^{i}$ for $i\in\mathbb{Z}_{6}$ , then $\text{int}(\nabla_{a}^{b})\cap\text{int}(\nabla_{t}^{c})=\emptyset$ .

Lemma 10 (Lemma 4 in [1]).

Let $s,t\in P$ and assume $t s$ is an edge of $\vec{\Theta}_{6}(P)$ . Then for $i\in\mathbb{Z}_{6}$ , we have

\sum\limits_{\begin{subarray}{c}ab\in\pi(s,t)\\ a\in C_{t}^{i}\end{subarray}}\|ab\|\leq\|\nabla_{t}^{s}\|

Instead of working with an empty triangle that forces the greedy path not to spiral as in [1], we will ignore any spiraling by only using the greedy path up to and including the first edge that crosses the boundary $R_{t}^{0}$ . Despite this change, the arguments in [1] can be applied in our setting to prove Lemma 11 which is a slightly modified version of Lemma 4 from [1].

Lemma 11.

Fix $j\in\mathbb{Z}_{6}$ and let $s,t,u,v\in P$ such that $u v$ is an edge of $\pi(s,t)$ and no edge of the truncated greedy path $\pi(s,t)_{u}$ crosses $R_{t}^{j}$ . For $i\in\mathbb{Z}_{6}$ , let $f_{i}$ denote the first vertex of $\pi(s,t)_{u}$ in $C_{t}^{i}$ . If no such vertex $f_{i}$ exists, let $f_{i}:=t$ . Then $\|\pi(s,t)_{v}\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page% -97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page% -97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2% svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}% \leq\sum_{i=0}^{5}\|f_{i}t\|_{\mathchoice{\includegraphics[height=6.02777pt]{% DirTh6-2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{% DirTh6-2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-% page-97.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2% svg.svg}}}$ .

Proof.

Suppose without loss of generality that $i=0$ . For any point $p$ below $t$ , let $p^{\prime}$ denote the intersection of the horizontal line through $p$ with the ray $R_{t}^{0}$ . We claim that if $a b$ and $c d$ are edges of $\pi(s,t)_{v}$ such that $a,c\in C_{t}^{0}$ , then the segments $a^{\prime}b^{\prime}$ and $c^{\prime}d^{\prime}$ are disjoint. Furthermore, both $a^{\prime}b^{\prime}$ and $c^{\prime}d^{\prime}$ are subsegments of $f_{0}^{\prime}t$ . This claim follows from Lemma 9 of [1] since the path $\pi(s,t)_{u}$ is assumed to not cross $R_{t}^{j}$ . We sum all edges with source in $C_{t}^{0}$ to obtain

\displaystyle\sum_{\begin{subarray}{c}ab\text{ on }\pi(s,t)_{v}\\ a\in C_{t}^{0}\end{subarray}}\|ab\|_{\mathchoice{\includegraphics[height=6.027% 77pt]{DirTh6-2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.027% 77pt]{DirTh6-2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{% DirTh6-2-page-97.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-% page-97.pdf2svg.svg}}}=\sum_{\begin{subarray}{c}ab\text{ on }\pi(s,t)_{v}\\ a\in C_{t}^{0}\end{subarray}}\|a^{\prime}b^{\prime}\|_{\mathchoice{% \includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}{\vbox{\hbox{% \includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}}}{% \includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}\leq\|f_{0}^% {\prime}t\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}=\|f_{% 0}t\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg% .svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg% .svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}.

The lemma follows by summing over the edges in all cones $C_{t}^{i}$ for $i\in\mathbb{Z}_{6}$ . $\hfill\blacktriangleleft$ For the rest of the section, we make Assumptions 12 and 13 to help us prove Theorem 3. For the cases when these assumptions do not hold, see the full version [5]. The first assumption roughly states that the greedy path from $y$ spirals counterclockwise around $t$ without making significant progress to $t$ . We define $u^{y}v^{y}$ to be the first edge of $\pi(y,t)$ which crosses $R_{t}^{0}$ . If such an edge does not exist, let $u^{y}:=t$ and $v^{y}:=t$ . Then the first assumption can be stated as follows:

Assumption 12.

There exists a vertex $q\in C_{t}^{5}$ on $\pi(y,t)_{v^{y}}$ with $\|qt\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}>y_{0}$ .

Our second assumption is that there is no edge $u v$ crossing $R_{t}^{5}$ such that $u\in T$ and $v\in C_{u}^{4}$ .

Assumption 13.

For every vertex $u\in T$ , we have $P\cap\text{int}(C_{t}^{0}\cap C_{u}^{4})\neq\emptyset$ .

Let $s x$ be the edge in $C_{s}^{4}$ . By Assumption 13, $x$ exists and $x\in C_{t}^{0}$ . Combining our two assumptions allows us to naturally consider two candidate paths, loosely referred to as the $x$ -path and the $y$ -path, and show that one of them is sufficiently short to force a contradiction with $d_{G}(s,t)>5\|st\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-% page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-% page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$ . Informally, the $x$ -path travels clockwise around $t$ , whereas the $y$ -path travels in the opposite direction. Where these two paths meet, they must compete for space. The lengths of the paths are primarily dictated by their long edges which cross cone boundaries around $t$ . These long edges come with large empty regions which squeeze the other path closer to $t$ . We formalize this intuition below.

Recall that $u^{y}v^{y}$ is the first edge of $\pi(y,t)$ that crosses the boundary $R_{t}^{0}$ . Consider the candidate path $s y$ concatenated with $\pi(y,t)_{v^{y}}$ , which we loosely refer to as the $y$ -path, ending at $v^{y}$ . Overall, the $y$ -path progresses counterclockwise about $t$ until $C_{t}^{5}$ , however it is still possible that the $y$ -path reverses direction and ends up crossing $R_{t}^{0}$ from $C_{t}^{1}$ to $C_{t}^{0}$ . Maintaining full generality, we may only assume that for some $i\in\{0,1\}$ , we have $u^{y}\in C_{t}^{i}$ and $v^{y}\in C_{t}^{1-i}$ , which follows from Lemma 8. In light of Lemma 11, we need not concern ourselves with every edge of this path. An upper bound can be established from only the first vertex of each cone. In fact, we only need to upper bound the value $\|f_{i}t\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$ where $f_{i}$ is the first vertex of $C_{t}^{i}$ , hence we look to the previous cone for structure. For $i\in\{1,2,3,4,5\}$ , let $y^{i}\in C_{t}^{i}$ be the vertex of $\pi(y,t)_{u^{y}}$ which maximizes $\|C_{t}^{i}\cap C_{y^{i}}^{i-2}\|$ . See Figure 7 for example.

Figure 7: In this example,

p

is the first vertex of

\pi(y,t)_{v^{y}}

in cone

C_{t}^{3}

. The highest vertex of

\pi(y,t)_{v^{y}}

in

C_{t}^{2}

is

y^{2}

by definition. The maximal triangle

C_{t}^{2}\cap C_{y^{2}}^{0}

is coloured orange, and

y_{2}=\|y^{2}t\|_{\mathchoice{\includegraphics[height=5.42496pt]{DirTh6-2-page% -97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=5.42496pt]{DirTh6-2-page% -97.pdf2svg.svg}}}}{\includegraphics[height=4.06871pt]{DirTh6-2-page-97.pdf2% svg.svg}}{\includegraphics[height=2.71248pt]{DirTh6-2-page-97.pdf2svg.svg}}}-% \|C_{t}^{2}\cap C_{y^{2}}^{0}\|

. Observation 14 implies that

y^{2}

has a greater

y

-coordinate than

p

, thus

\|C_{t}^{2}\cap C_{y^{2}}^{0}\|

provides an upper bound on

\|pt\|_{\mathchoice{\includegraphics[height=5.42496pt]{DirTh6-2-page-97.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=5.42496pt]{DirTh6-2-page-97.pdf2% svg.svg}}}}{\includegraphics[height=4.06871pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=2.71248pt]{DirTh6-2-page-97.pdf2svg.svg}}}

.

Observation 14.

For $i\in\{1,2,3,4,5\}$ , no vertex of $\pi(y,t)_{y^{i}}$ is in $\text{int}(C_{t}^{i+1})$ .

Proof.

The observation holds for $i=1$ since $y^{1}=y$ . Then for $i\in\{2,3,4,5\}$ , consider the first vertex $v$ of $C_{t}^{i+1}$ on $\pi(y,t)_{u^{y}}$ . Then $y^{i}$ and $t$ must be on opposite sides of the line $R_{v}^{i-1}\cup R_{v}^{i+2}$ , which implies $\|y^{i}t\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}>\|vt% \|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg.% svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg.% svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$ , meaning that $y^{i}$ appears before $v$ on $\pi(y,t)_{u^{y}}$ . $\hfill\blacktriangleleft$ Observation 14 implies $y^{1},y^{2},y^{3},y^{4},y^{5}$ appear in order on $\pi(y,t)_{u^{y}}$ . Intuitively, $y^{i}$ is the head of a long edge whose tail is in the previous cone $C_{t}^{i-1}$ . Indeed, if the tail was in the same cone as $y^{i}$ , then $\|C_{t}^{i}\cap C_{y^{i}}^{i-2}\|$ would not be maximal. We define the distance $y_{i}$ from $y^{i}$ to $C_{t}^{i+1}$ as $y_{i}:=\|C_{t}^{i}\cap C_{y^{i}}^{i+2}\|$ . Equivalently, $y_{i}=\|y^{i}t\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page% -97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page% -97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2% svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}-% \|C_{t}^{i}\cap C_{y^{i}}^{i-2}\|$ . By Assumption 12, the $y$ -path must pass through cones $C_{t}^{1},...,C_{t}^{5}$ , hence $y_{i}$ is well-defined for $i\in\{1,2,3,4,5\}$ . Also notice that the region $\text{int}(C_{t}^{i}\cap C_{y^{i}}^{i-2})$ is empty since $y^{i}$ is necessarily the head of an edge from $C_{t}^{i-1}$ . Next, for each $i\in\mathbb{Z}_{6}$ , we let $Y_{i}$ be the value of $\|ut\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$ where $u$ is the first vertex of $\pi(y,t)_{u^{y}}$ with $u\in C_{t}^{i}$ . If no such vertex $u\in C_{t}^{i}$ exists, then $Y_{i}:=0$ . First, we have $Y_{1}=\|yt\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}\leq 1% -y_{0}$ . Next, for $i\in\{1,2,3,4,5\}$ , cone $C_{t}^{i+1}$ can only be visited from cone $C_{t}^{i}$ on $\pi(y,t)_{u^{y}}$ , therefore we see that for $i\in\{1,2,3,4,5\}$ ,

\displaystyle y_{0}+Y_{1}\leq 1\qquad\text{and}\qquad y_{i}+Y_{i+1}\leq y_{i}+% \|C_{t}^{i}\cap C_{y^{i}}^{i-2}\|=\|y^{i}t\|_{\mathchoice{\includegraphics[hei% ght=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[hei% ght=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.5208% 3pt]{DirTh6-2-page-97.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-% 2-page-97.pdf2svg.svg}}}\leq Y_{i}

(4)

We include these inequalities in our system which will eventually be proven infeasible. Next we will discuss the second candidate path: the $x$ -path. Recall $s x$ is the edge in $C_{s}^{4}\cap C_{t}^{0}$ . We will define the analogous variables for $x$ as we did for $y$ . Let $u^{x}v^{x}$ be the first edge of $\pi(x,t)$ that crosses $R_{t}^{0}$ . As before, Lemma 8 implies that for some $i\in\{0,1\}$ , we have $u^{x}\in C_{t}^{i}$ and $v^{x}\in C_{t}^{1-i}$ . If no such crossing exists, then set $u^{x}:=t$ and $v^{x}:=t$ . For $i\in\{0,5,4,3,2\}$ , let $x^{i}\in C_{t}^{i}$ be the vertex of $\pi(x,t)_{u^{x}}$ which maximizes $\|C_{t}^{i}\cap C_{x^{i}}^{i+2}\|$ . We define the distance $x_{i}$ from $x^{i}$ to $C_{t}^{i-1}$ as $x_{i}:=\|C_{t}^{i}\cap C_{x^{i}}^{i-2}\|$ . If no such $x^{i}$ exists, then define $x_{i}:=0$ . However, we will later argue in Claim 19 that the vertices $x^{0},x^{5},x^{4},x^{3}$ must exist, otherwise the $x$ -path is sufficiently short to force a contradiction. Observe that for $i\in\{5,4,3,2\}$ the region $C_{t}^{i}\cap C_{x^{i}}^{i+2}$ is empty since $x^{i}$ is the head of an edge from $C_{t}^{i+1}$ . Next, for each $i\in\mathbb{Z}_{6}$ , we let $X_{i}$ be the value of $\|ut\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$ where $u$ is the first vertex of $\pi(x,t)_{u^{x}}$ with $u\in C_{t}^{i}$ . If no such vertex $u$ exists, then $X_{i}:=0$ . Since greedy paths decrease in $\|\cdot\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf% 2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf% 2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}% {\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$ -norm, then we have $X_{0}=\|xt\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}\leq 1$ . Next, for $i\in\{5,4,3,2,1\}$ , if $v$ is the first vertex of $\pi(x,t)_{u^{x}}$ in $C_{t}^{i}$ , then its predecessor $u$ must be in cone $C_{t}^{i+1}$ , therefore we see that for $i\in\{5,4,3,2,1\}$ ,

\displaystyle X_{0}\leq 1\quad\text{and}\quad x_{i+1}+X_{i}\leq x_{i+1}+\|C_{t% }^{i+1}\cap C_{x^{i+1}}^{i+3}\|=\|x^{i+1}t\|_{\mathchoice{\includegraphics[hei% ght=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[hei% ght=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.5208% 3pt]{DirTh6-2-page-97.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-% 2-page-97.pdf2svg.svg}}}\leq X_{i+1}.

(5)

Intuitively, the only vertices in cone $C_{t}^{i}$ that are important to us are $x^{i}$ and $y^{i}$ . Now we consider possible paths from $s$ to $t$ . We could take the $y$ -path from $s$ to $v^{y}$ , then apply induction at $v^{y}$ . By Lemma 11, this yields

$\displaystyle 5-2.5y_{0}$	$\displaystyle\leq d_{G}(s,t)$
	$\displaystyle\leq\\|sy\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6% -2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6% -2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97% .pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg% }}}+\\|\pi(y,t)_{v^{y}}\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh% 6-2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh% 6-2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-9% 7.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.% svg}}}+d_{G}(v^{y},t)$
	$\displaystyle\leq(1-y_{1})+(Y_{1}+Y_{2}+Y_{3}+Y_{4}+Y_{5}+Y_{0})+5\|\|v^{y}t\|\|_{% \mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.svg}}}% }{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}.$	(6)

On the other hand, we could instead follow the $x$ -path from $s$ to $v^{x}$ , then apply induction at $v^{x}$ . Similarly, we obtain

$\displaystyle 5-2.5y_{0}$	$\displaystyle\leq d_{G}(s,t)$
	$\displaystyle\leq\\|sx\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6% -2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6% -2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97% .pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg% }}}+\\|\pi(x,t)_{v^{x}}\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh% 6-2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh% 6-2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-9% 7.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.% svg}}}+d_{G}(v^{x},t)$
	$\displaystyle\leq(1-y_{0}-x_{0})+(X_{0}+X_{5}+X_{4}+X_{3}+X_{2}+X_{1})+5\|\|v^{x% }t\|\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.% svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.% svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}.$	(7)

While we have proven several inequalities (2),(4),(5),(6),(7), they are not yet strong enough to form an infeasible system. First, notice that since $R$ may not contain vertices, then $u^{y}v^{y}$ must cross both $B_{t}^{0}$ and $B_{t}^{1}$ . By the following lemma, this implies that the edge $u^{y}v^{y}$ makes significant progress towards $t$ .

Lemma 15.

Let $u,v,t\in P$ with edge $u v$ contained in $\nabla_{u}^{t}$ . Assume $u v$ crosses both $B_{t}^{0}$ and $B_{t}^{1}$ , then $2\|vt\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}\leq\|uv\|_{% \mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}}% }{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$ .

Proof.

Suppose without loss of generality that $u\in C_{t}^{0}$ with $u$ to the left of $B_{t}^{0}$ , and $v\in C_{t}^{1}$ with $v$ above $B_{t}^{1}$ . See Figure 8. Consider the point $t^{\prime}:=B_{t}^{0}\cap R_{v}^{5}$ . Since $u$ is to the left of $B_{t}^{0}$ , then the segment $vt^{\prime}$ is contained in $\nabla_{u}^{v}$ , hence $\|vt^{\prime}\|_{2}\leq\|\nabla_{u}^{v}\|=\|uv\|_{\mathchoice{\includegraphics% [height=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics% [height=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.% 52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{% DirTh6-2-page-97.pdf2svg.svg}}}$ . On the other hand, consider the point $v^{\prime}:=R_{t}^{1}\cap B_{v}^{3}$ . Then considering that $vt^{\prime}$ and $v^{\prime}t$ have respective slopes $\sqrt{3}$ and $0$ , then we have $2\|vt\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}=2\|v^{% \prime}t\|_{2}=\|vt^{\prime}\|_{2}\leq\|uv\|_{\mathchoice{\includegraphics[hei% ght=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[hei% ght=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.5208% 3pt]{DirTh6-2-page-97.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-% 2-page-97.pdf2svg.svg}}}$ .

Figure 8: Lemma 15 where

u\in C_{t}^{0}

with

u

to the left of

B_{t}^{0}

, and

v\in C_{t}^{1}

with

v

above

B_{t}^{1}

.

$\hfill\blacktriangleleft$

Lemma 15 quantifies the toll required for an edge to cross the empty region. Intuitively, the distance to $t$ is halved each time the empty region $R$ is crossed. In order to also apply Lemma 15 to $u^{x}v^{x}$ , we require two observations, which follow from Assumptions 12 and 13.

Observation 16.

If $x^{1}$ exists, then $\|x^{1}t\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}\leq 1% -y_{0}$ .

Proof.

Suppose on the contrary that $\|x^{1}t\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}>1-y_{0}$ . See Figure 9. Since greedy paths decrease in $\|\cdot\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf% 2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf% 2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}% {\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$ -norm to their destination, then $\|y^{i}t\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$ is monotonically decreasing, whereas $\|x^{i}t\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$ is monotonically increasing for $i\in\{1,2,3,4,5\}$ . This means that $\|y^{i}t\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}\leq\|% y^{1}t\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}\leq 1-y_{0}% <\|x^{1}t\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}\leq\|% x^{i}t\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$ . In particular, the empty regions $C_{t}^{i}\cap C_{x^{i}}^{i+2}$ for $i\in\{2,3,4\}$ imply that $Y_{3}\leq x_{2}$ , $Y_{4}\leq x_{3}$ , and $Y_{5}\leq x_{4}$ . Assumption 12 implies $Y_{5}\geq y_{0}$ , therefore (4) implies $\min(x_{2},x_{3},x_{4})\geq y_{0}$ . However this yields $1-y_{0}<\|x^{1}t\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-% page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-% page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}% }}<1-x_{0}-x_{5}-x_{4}-x_{3}-x_{2}\leq 1-3y_{0}$ , which implies $y_{0}<0$ . This is a contradiction, hence we may assume $\|x^{1}t\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}\leq 1% -y_{0}$ for the rest of the proof.

Figure 9: Observation 16: From Assumption 12, there cannot exist

x^{1}

such that

\|x^{1}t\|>1-y_{0}

.

$\hfill\blacktriangleleft$

Observation 17.

There is no edge $u v$ on $\pi(x,t)_{v^{x}}$ with $u\in C_{t}^{5}$ and $v\in T$ .

Proof.

If there were such an edge $u v$ on $\pi(x,t)_{v^{x}}$ with $u\in C_{t}^{5}$ and $v\in T$ , the empty region $\text{int}(\nabla_{u}^{v})$ contradicts Assumption 13. See Figure 10.

Figure 10: Observation 17: If

u v

is an edge from

C_{t}^{5}

to

T

, then the region

C_{v}^{4}\cap C_{t}^{0}

contains no vertices in its interior, contradicting Assumption 13.

$\hfill\blacktriangleleft$

Observations 16 and 17 together imply that the edge $u^{x}v^{x}$ crosses both $B_{t}^{0}$ and $B_{t}^{1}$ since the interior of region $R$ is empty by Lemma 7. Therefore Lemma 15 applies to $u^{x}v^{x}$ as well. Furthermore, we can ensure that $\|v^{x}t\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}\leq x% _{0}$ by the following claim.

Claim 18.

There is no vertex to the left of $B_{t}^{0}$ in the interior of $C_{x}^{2}$ .

Proof.

Assume there is such a vertex $p\in C_{x}^{2}$ to the left of $B_{t}^{0}$ . Note that we must have $p\in C_{s}^{3}$ since $C_{x}^{2}\cap C_{s}^{4}\subseteq\nabla_{s}^{x}$ and $\nabla_{s}^{x}$ contains no vertices. This means that $p$ is above $\nabla_{s}^{y}$ , yielding $\|pt\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}\leq y_{1}$ . See Figure 11.

Figure 11: If there is a vertex to the left of

B_{t}^{0}

in

C_{x}^{2}

(the dark grey region), then we can form a path that passes through

s,u^{1},u^{2},u^{3},t

. Induction is used to bound

d_{G}(s,u^{1})

and

d_{G}(u^{3},t)

, whereas

u^{1}u^{2}

and

u^{2}u^{3}

are edges in

G

(in green).

Let $u^{1}$ be the vertex of $T:=C_{t}^{0}\cap C_{s}^{2}$ minimizing $\|u^{1}t\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$ . Then we take the edge $u^{1}u^{2}$ in $C_{u^{1}}^{4}$ . By Assumption 13, we have $u^{2}\in C_{t}^{0}$ . If $u^{2}\in C_{x}^{2}$ , then set $u^{3}:=u^{2}$ . Otherwise take the edge $u^{2}u^{3}$ in $C_{u^{2}}^{2}$ . We must have $u^{3}\in C_{s}^{3}$ , hence we apply induction from $u^{3}$ to $t$ . This yields

$\displaystyle 5-2.5y_{0}$	$\displaystyle<d_{G}(s,t)$
	$\displaystyle\leq d_{G}(s,u^{1})+\\|u^{1}u^{2}\\|_{\mathchoice{\includegraphics[% height=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[% height=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.5% 2083pt]{DirTh6-2-page-97.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{% DirTh6-2-page-97.pdf2svg.svg}}}+\\|u^{2}u^{3}\\|_{\mathchoice{\includegraphics[h% eight=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[h% eight=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52% 083pt]{DirTh6-2-page-97.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh% 6-2-page-97.pdf2svg.svg}}}+d_{G}(u^{3},t)$
	$\displaystyle\leq 5y_{0}+1+1+5y_{1}.$	(8)

However, the system of inequalities (2,8) is infeasible. Therefore we may assume that the region $C_{x}^{2}\cap C_{t}^{0}$ to the left of $B_{t}^{0}$ is empty for the remainder of the proof. $\hfill\vartriangleleft$ In order to further restrict the set of solutions to our linear system of inequalities towards infeasibility, we will consider several cases with more granularity. We will first consider the direction in which the edge $u^{y}v^{y}$ crosses the boundary $R_{t}^{0}$ in order to strengthen our upper bound on $\|v^{y}t\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$ . Recall that $5\|v^{y}t\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$ accounts for the path from $v^{y}$ to $t$ by induction, hence it is an important quantity to reduce. We will apply the same analysis to $u^{x}v^{x}$ to also upper bound $\|v^{x}t\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$ , then lastly we will consider the trade-off between the $x$ -path and $y$ -path. In Figure 12, we show an example of the $x$ -path and $y$ -path that compete for space.

Figure 12: Top Left: The colour coding for edges based on direction. Right: The grey region

R

contains no vertices in its interior by Lemma 7. The triangular regions are coloured according to their edge direction. This example shows the case when

v^{y}\in C_{t}^{1}

(case

Y1

),

v^{x}\in C_{t}^{0}

(case

X0

), and

j=3

(case J3). Notice that the empty turquoise region

C_{t}^{3}\cap C_{y^{3}}^{1}

constrains the position of

x^{3}

, forcing

x^{2}

to be considerably closer to

t

. Lower Left: This enlarged view shows the edges that cross the empty grey region

R

. Notice that the edges

u^{x}v^{x}

and

u^{y}v^{y}

both make considerable progress towards

t

(quantified in Lemma 15).

Next, we show in Claim 19 that the $x$ -path must visit the cone $C_{t}^{3}$ .

Claim 19.

The path $\pi(x,t)_{v^{x}}$ must contain a vertex in $C_{t}^{3}$ .

Proof.

If the claim did not hold, then $u^{x}v^{x}$ would necessarily cross $R$ in the counterclockwise direction. See Figure 13.

Figure 13: Claim 19: If

\pi(x,t)_{v^{x}}

does not enter

C_{t}^{3}

, then we can form an infeasible system of linear inequalities.

If $\pi(x,t)_{v^{x}}\cap C_{t}^{5}\neq\emptyset$ , then we use Lemma 11 and apply induction at $v^{x}$ to obtain

$\displaystyle 5-2.5y_{0}$	$\displaystyle<d_{G}(s,t)$
	$\displaystyle\leq\\|sx\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6% -2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6% -2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97% .pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg% }}}+\\|\pi(x,t)_{v^{x}}\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh% 6-2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh% 6-2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-9% 7.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.% svg}}}+d_{G}(v^{x},t)$
	$\displaystyle\leq(1-x_{0}-y_{0})+(X_{0}+X_{5}+X_{4})+5\|\|v^{x}t\|\|_{\mathchoice{% \includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}{\vbox{\hbox{% \includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}}}{% \includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$
	$\displaystyle\leq(1-x_{0}-y_{0})+1+(1-x_{0})+(1-x_{0}-x_{5})+5\min(x_{0},\frac% {x_{5}}{2}).$	(9)

However, the linear system (2,9) is infeasible. On the other hand if $\pi(x,t)_{v^{x}}\cap C_{t}^{5}=\emptyset$ , then

$\displaystyle d_{G}(s,t)$	$\displaystyle\leq\\|sx\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6% -2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6% -2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97% .pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg% }}}+\\|\pi(x,t)_{v^{x}}\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh% 6-2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh% 6-2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-9% 7.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.% svg}}}+d_{G}(v^{x},t)$
	$\displaystyle\leq(1-x_{0}-y_{0})+X_{0}+5\|\|v^{x}t\|\|_{\mathchoice{% \includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}{\vbox{\hbox{% \includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}}}{% \includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$
	$\displaystyle\leq(1-x_{0}-y_{0})+1+5x_{0}$
	$\displaystyle\leq 4-y_{0}$	since $x_{0}\leq 1/2$ ,
	$\displaystyle\leq 5-2.5y_{0}$	since $y_{0}\leq 1/2$ .

which is a contradiction. To summarize, $\pi(x,t)_{v^{x}}$ must enter $C_{t}^{3}$ . $\hfill\vartriangleleft$ First, notice that $u^{y}v^{y}$ can cross $R_{t}^{0}$ either in the clockwise or counterclockwise direction:

Case Y0: $v^{y}\in C_{t}^{0}$ .

Then we must have $u^{y}\in C_{t}^{1}$ . We obtain the following two inequalities:

	$\displaystyle\|\|v^{y}t\|\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6% -2-page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6% -2-page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98% .pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg% }}}$	$\displaystyle\leq y_{1},$	by empty region $\text{int}(\nabla_{s}^{y})$ .		(10)
	$\displaystyle\|\|v^{y}t\|\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6% -2-page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6% -2-page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98% .pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg% }}}$	$\displaystyle\leq\frac{1}{2}\min(y_{2},y_{3},y_{4}),$	by Assumption 12 and Lemma 15.		(11)

Case Y1: $v^{y}\in C_{t}^{1}$ .

Then we must have $u^{y}\in C_{t}^{0}$ . We obtain

	$\displaystyle\|\|v^{y}t\|\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6% -2-page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6% -2-page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98% .pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg% }}}$	$\displaystyle\leq x_{0},$	by Claim 18.		(12)
	$\displaystyle\|\|v^{y}t\|\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6% -2-page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6% -2-page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98% .pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg% }}}$	$\displaystyle\leq\frac{Y_{0}}{2},$	by Lemma 15.		(13)

Similarly, $u^{x}v^{x}$ can also cross $R_{t}^{0}$ in one of two possible ways.

Case X0: $v^{x}\in C_{t}^{0}$ .

Then we have

	$\displaystyle\|\|v^{x}t\|\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6% -2-page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6% -2-page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98% .pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg% }}}$	$\displaystyle\leq y_{1},$	by Observation 16 and empty region $\text{int}(\nabla_{s}^{y})$ .		(14)
	$\displaystyle\|\|v^{x}t\|\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6% -2-page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6% -2-page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98% .pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg% }}}$	$\displaystyle\leq\frac{X_{1}}{2},$	by Lemma 15.		(15)

Case X1: $v^{x}\in C_{t}^{1}$ .

Then $u^{y}\in C_{t}^{0}$ . We have

	$\displaystyle\|\|v^{x}t\|\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6% -2-page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6% -2-page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98% .pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg% }}}$	$\displaystyle\leq x_{0},$	by Claim 18 and 17.		(16)
	$\displaystyle\|\|v^{x}t\|\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6% -2-page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6% -2-page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98% .pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg% }}}$	$\displaystyle\leq\frac{1}{2}\min(x_{5},x_{4},x_{3}),$	by Claim 19 and Lemma 15.		(17)

Next, we will derive several useful inequalities that reflect the balance between the two candidate paths. Intuitively, if $\pi(y,t)_{v^{y}}$ is long, then the empty regions $C_{t}^{i}\cap C_{y^{i}}^{i-2}$ must be large, leaving no room for the other path $\pi(x,t)_{v^{x}}$ . We formalize this trade-off as follows. Let $j$ be the greatest index in $\{2,3,4,5\}$ such that $\|C_{t}^{j}\cap C_{y^{j}}^{j-2}\|>x_{j}$ . For example when $j=3$ , see Figure 12.

Case: No such $𝒋$ exists.

Then by definition we must have

\displaystyle Y_{i+1}\leq\|C_{t}^{i}\cap C_{y^{i}}^{i-2}\|\leq x_{i}\quad\text% {for }2\leq i\leq 5.

(18)

Case: $j\in\{2,3,4,5\}$ .

As $j$ is maximal, then $\|C_{t}^{i}\cap C_{y^{i}}^{i-2}\|\leq x_{i}$ for $j<i\leq 5$ . Next, since $\|C_{t}^{j}\cap C_{y^{j}}^{j-2}\|>x_{j}$ , then we must have $\|y^{k}t\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}>\|x^{% k}t\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg% .svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg% .svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$ for $2\leq k\leq j$ . By the empty regions $C_{t}^{i}\cap C_{y^{i}}^{i-2}$ , we must have

\displaystyle Y_{i+1}\leq\|C_{t}^{i}\cap C_{y^{i}}^{i-2}\|\leq x_{i}\quad\text% {for }j<i\leq 5,\quad\text{ and }\quad X_{k-1}\leq y_{k}\quad\text{for }2\leq k% \leq j.

(19)

We denote the cases where $j\in\{2,3,4,5\}$ as J2, J3, J4, J5, and observe that for each case, we yield four inequalities from (19).

Under Assumptions 12 and 13 we have the following possibility space: $\{\text{Y0, Y1}\}\times\{\text{X0, X1}\}\times\{\eqref{noj},\text{ J2, J3, J4,% J5}\}$ . In total there are $2\times 2\times 5=20$ possibilities, and in every case, the inequalities (2), (4), (5), (6), (7) also hold. It can be shown that the linear system of inequalities is infeasible for $16$ of the $20$ possibilities. In the full version [5], we show that for the remaining four cases, we can define a third candidate path which is sufficiently short for a contradiction. These remaining four cases are (X1, Y1, J2), (X1, Y1, J3), (X1, Y1, J4), (X0, Y0, J3).

References

[1] Hugo A. Akitaya, Ahmad Biniaz, and Prosenjit Bose. On the spanning and routing ratios of the directed $\Theta$ ${}_{\mbox{6}}$ -graph. Comput. Geom., 105-106:101881, 2022. doi:10.1016/j.comgeo.2022.101881.
[2] Luis Barba, Prosenjit Bose, Jean-Lou De Carufel, André van Renssen, and Sander Verdonschot. On the stretch factor of the theta-4 graph. In WADS, volume 8037 of Lecture Notes in Computer Science, pages 109–120. Springer, 2013. doi:10.1007/978-3-642-40104-6_10.
[3] Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, and Ljubomir Perkovic. Tight stretch factors for L ${}_{\mbox{1}}$ - and L ${}_{\mbox{{$\infty$}}}$ -Delaunay triangulations. Comput. Geom., 48(3):237–250, 2015. doi:10.1016/j.comgeo.2014.10.005.
[4] Prosenjit Bose, Jean-Lou De Carufel, Darryl Hill, and Michiel Smid. On the spanning and routing ratio of the directed theta-four graph. Discret. Comput. Geom., 71(3):872–892, 2024. doi:10.1007/s00454-023-00597-8.
[5] Prosenjit Bose, Jean-Lou De Carufel, Darryl Hill, and John Stuart. The spanning ratio of the directed $\theta_{6}$ -graph is 5, 2026. arXiv:2603.09048.
[6] 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. Theor. Comput. Sci., 616:70–93, 2016. doi:10.1016/j.tcs.2015.12.017.
[7] Prosenjit Bose, Jean-Lou De Carufel, and Sandrine Njoo. The exact spanning ratio of the parallelogram Delaunay graph. Theor. Comput. Sci., 1037:115152, 2025. doi:10.1016/j.tcs.2025.115152.
[8] Prosenjit Bose and André van Renssen. Upper bounds on the spanning ratio of constrained theta-graphs. In LATIN, volume 8392 of Lecture Notes in Computer Science, pages 108–119. Springer, 2014. doi:10.1007/978-3-642-54423-1_10.
[9] Paul Chew. There is a planar graph almost as good as the complete graph. In SCG, pages 169–177. ACM, 1986. doi:10.1145/10515.10534.
[10] Paul Chew. There are planar graphs almost as good as the complete graph. J. Comput. Syst. Sci., 39(2):205–219, 1989. doi:10.1016/0022-0000(89)90044-5.
[11] K. Clarkson. Approximation algorithms for shortest path motion planning. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC ’87, pages 56–65, New York, NY, USA, 1987. Association for Computing Machinery. doi:10.1145/28395.28402.
[12] David P. Dobkin, Steven J. Friedman, and Kenneth J. Supowit. Delaunay graphs are almost as good as complete graphs. Discret. Comput. Geom., 5:399–407, 1990. doi:10.1007/BF02187801.
[13] J. Mark Keil and Carl A. Gutwin. Classes of graphs which approximate the complete Euclidean graph. Discret. Comput. Geom., 7(1):13–28, December 1992. doi:10.1007/BF02187821.
[14] Anna Lubiw and Debajyoti Mondal. Construction and local routing for angle-monotone graphs. J. Graph Algorithms Appl., 23(2):345–369, 2019. doi:10.7155/jgaa.00494.
[15] Giri Narasimhan and Michiel Smid. Geometric Spanner Networks. Cambridge University Press, 2007. doi:10.1017/CBO9780511546884.
[16] Ljubomir Perkovic, Michael Dennis, and Duru Türkoglu. The stretch factor of hexagon-Delaunay triangulations. J. Comput. Geom., 12(2):86–125, 2021. doi:10.20382/jocg.v12i2a5.
[17] J. Ruppert and R. Seidel. Approximating the D-dimensional complete Euclidean graph. In Proceedings of the 3rd Annual Canadian Conference on Computational Geometry, pages 207–210, 1991. URL: https://cccg.ca/proceedings/1991/paper50.pdf.
[18] John Stuart, Jean-Lou De Carufel, and Prosenjit Bose. The exact routing and spanning ratio of arbitrary triangle Delaunay graphs. In Rahnuma Islam Nishat, editor, Proceedings of the 36th Canadian Conference on Computational Geometry, CCCG 2024, Brock University, St. Catharines, Canada, July 17-19, 2024, pages 83–89, 2024. doi:10.48550/arXiv.2506.12625.
[19] André van Renssen, Yuan Sha, Yucheng Sun, and Sampson Wong. The tight spanning ratio of the rectangle Delaunay triangulation. In ESA, volume 274 of LIPIcs, pages 99:1–99:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.ESA.2023.99.
[20] Ge Xia. The stretch factor of the Delaunay triangulation is less than 1.998. SIAM J. Comput., 42(4):1620–1659, 2013. doi:10.1137/110832458.
[21] Ge Xia and Liang Zhang. Toward the tight bound of the stretch factor of Delaunay triangulations. In Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, Toronto, Ontario, Canada, August 10-12, 2011, 2011. URL: http://www.cccg.ca/proceedings/2011/papers/paper57.pdf.
[22] Andrew Chi-Chih Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Comput., 11(4):721–736, 1982. doi:10.1137/0211059.

[bib.bib1] [1] Hugo A. Akitaya, Ahmad Biniaz, and Prosenjit Bose. On the spanning and routing ratios of the directed $\Theta$ ${}_{\mbox{6}}$ -graph. Comput. Geom., 105-106:101881, 2022. doi:10.1016/j.comgeo.2022.101881.

[bib.bib2] [2] Luis Barba, Prosenjit Bose, Jean-Lou De Carufel, André van Renssen, and Sander Verdonschot. On the stretch factor of the theta-4 graph. In WADS, volume 8037 of Lecture Notes in Computer Science, pages 109–120. Springer, 2013. doi:10.1007/978-3-642-40104-6_10.

[bib.bib3] [3] Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, and Ljubomir Perkovic. Tight stretch factors for L ${}_{\mbox{1}}$ - and L ${}_{\mbox{{$\infty$}}}$ -Delaunay triangulations. Comput. Geom., 48(3):237–250, 2015. doi:10.1016/j.comgeo.2014.10.005.

[bib.bib4] [4] Prosenjit Bose, Jean-Lou De Carufel, Darryl Hill, and Michiel Smid. On the spanning and routing ratio of the directed theta-four graph. Discret. Comput. Geom., 71(3):872–892, 2024. doi:10.1007/s00454-023-00597-8.

[bib.bib5] [5] Prosenjit Bose, Jean-Lou De Carufel, Darryl Hill, and John Stuart. The spanning ratio of the directed $\theta_{6}$ -graph is 5, 2026. arXiv:2603.09048.

[bib.bib6] [6] 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. Theor. Comput. Sci., 616:70–93, 2016. doi:10.1016/j.tcs.2015.12.017.

[bib.bib7] [7] Prosenjit Bose, Jean-Lou De Carufel, and Sandrine Njoo. The exact spanning ratio of the parallelogram Delaunay graph. Theor. Comput. Sci., 1037:115152, 2025. doi:10.1016/j.tcs.2025.115152.

[bib.bib8] [8] Prosenjit Bose and André van Renssen. Upper bounds on the spanning ratio of constrained theta-graphs. In LATIN, volume 8392 of Lecture Notes in Computer Science, pages 108–119. Springer, 2014. doi:10.1007/978-3-642-54423-1_10.

[bib.bib9] [9] Paul Chew. There is a planar graph almost as good as the complete graph. In SCG, pages 169–177. ACM, 1986. doi:10.1145/10515.10534.

[bib.bib10] [10] Paul Chew. There are planar graphs almost as good as the complete graph. J. Comput. Syst. Sci., 39(2):205–219, 1989. doi:10.1016/0022-0000(89)90044-5.

[bib.bib11] [11] K. Clarkson. Approximation algorithms for shortest path motion planning. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC ’87, pages 56–65, New York, NY, USA, 1987. Association for Computing Machinery. doi:10.1145/28395.28402.

[bib.bib12] [12] David P. Dobkin, Steven J. Friedman, and Kenneth J. Supowit. Delaunay graphs are almost as good as complete graphs. Discret. Comput. Geom., 5:399–407, 1990. doi:10.1007/BF02187801.

[bib.bib13] [13] J. Mark Keil and Carl A. Gutwin. Classes of graphs which approximate the complete Euclidean graph. Discret. Comput. Geom., 7(1):13–28, December 1992. doi:10.1007/BF02187821.

[bib.bib14] [14] Anna Lubiw and Debajyoti Mondal. Construction and local routing for angle-monotone graphs. J. Graph Algorithms Appl., 23(2):345–369, 2019. doi:10.7155/jgaa.00494.

[bib.bib15] [15] Giri Narasimhan and Michiel Smid. Geometric Spanner Networks. Cambridge University Press, 2007. doi:10.1017/CBO9780511546884.

[bib.bib16] [16] Ljubomir Perkovic, Michael Dennis, and Duru Türkoglu. The stretch factor of hexagon-Delaunay triangulations. J. Comput. Geom., 12(2):86–125, 2021. doi:10.20382/jocg.v12i2a5.

[bib.bib17] [17] J. Ruppert and R. Seidel. Approximating the D-dimensional complete Euclidean graph. In Proceedings of the 3rd Annual Canadian Conference on Computational Geometry, pages 207–210, 1991. URL: https://cccg.ca/proceedings/1991/paper50.pdf.

[bib.bib18] [18] John Stuart, Jean-Lou De Carufel, and Prosenjit Bose. The exact routing and spanning ratio of arbitrary triangle Delaunay graphs. In Rahnuma Islam Nishat, editor, Proceedings of the 36th Canadian Conference on Computational Geometry, CCCG 2024, Brock University, St. Catharines, Canada, July 17-19, 2024, pages 83–89, 2024. doi:10.48550/arXiv.2506.12625.

[bib.bib19] [19] André van Renssen, Yuan Sha, Yucheng Sun, and Sampson Wong. The tight spanning ratio of the rectangle Delaunay triangulation. In ESA, volume 274 of LIPIcs, pages 99:1–99:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.ESA.2023.99.

[bib.bib20] [20] Ge Xia. The stretch factor of the Delaunay triangulation is less than 1.998. SIAM J. Comput., 42(4):1620–1659, 2013. doi:10.1137/110832458.

[bib.bib21] [21] Ge Xia and Liang Zhang. Toward the tight bound of the stretch factor of Delaunay triangulations. In Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, Toronto, Ontario, Canada, August 10-12, 2011, 2011. URL: http://www.cccg.ca/proceedings/2011/papers/paper57.pdf.

[bib.bib22] [22] Andrew Chi-Chih Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Comput., 11(4):721–736, 1982. doi:10.1137/0211059.

$\displaystyle d_{G}(s,t)$	$\displaystyle\leq\\|sy\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6% -2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6% -2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97% .pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg% }}}+d_{G}(y,t)$	by triangle inequality,
	$\displaystyle\leq 1+5y_{0}$	by induction as $\\|yt\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}\leq\\|yt\\|_{% \mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-97.pdf2svg.svg}}}% }{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}=\\|\nabla_{t% }^{y}\\|\leq\\|T\\|$
	$\displaystyle<5\\|st\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2% -page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2% -page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$	since $y_{0}\leq 0.5$ and $5-2.5y_{0}=5\\|st\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-% page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-% page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg}}}$ .

$\displaystyle d_{G}(s,t)$	$\displaystyle\leq\\|sy\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6% -2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6% -2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97% .pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg% }}}+d_{G}(y,t)$	by triangle inequality,
	$\displaystyle\leq 2(\\|st\\|_{\mathchoice{\includegraphics[height=6.02777pt]{% DirTh6-2-page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{% DirTh6-2-page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-% page-98.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2% svg.svg}}}-\\|yt\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-% page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-% page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}% }})+5\\|yt\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$	by Lemma 5 and induction,
	$\displaystyle=2\\|st\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2% -page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2% -page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}% }}+3\\|yt\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$
	$\displaystyle<5\\|st\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2% -page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2% -page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$	since $\\|yt\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}<\\|st\\|_{% \mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.svg}}}% }{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$ .

$\displaystyle d_{G}(s,t)$	$\displaystyle\leq\\|sx\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6% -2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6% -2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97% .pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg% }}}+d_{G}(x,t)$	by triangle inequality,
	$\displaystyle\leq 2(\\|st\\|_{\mathchoice{\includegraphics[height=6.02777pt]{% DirTh6-2-page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{% DirTh6-2-page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-% page-98.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2% svg.svg}}}-\\|xt\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-% page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-% page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}% }})+5\\|xt\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$	by Lemma 5 and induction,
	$\displaystyle=2\\|st\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2% -page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2% -page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}% }}+3\\|xt\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$
	$\displaystyle<5\\|st\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2% -page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2% -page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$	since $\\|xt\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}<\\|st\\|_{% \mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.svg}}}% }{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$ .

$\displaystyle d_{G}(s,t)$	$\displaystyle\leq\\|sx\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6% -2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6% -2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-97% .pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2svg.svg% }}}+d_{G}(x,t)$	by triangle inequality,
	$\displaystyle\leq\\|sq^{0}\\|_{\mathchoice{\includegraphics[height=6.02777pt]{% DirTh6-2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{% DirTh6-2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-% page-97.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2% svg.svg}}}+5\\|xt\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-% page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-% page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$	by induction,
	$\displaystyle\leq 2\\|sq^{1}\\|_{\mathchoice{\includegraphics[height=6.02777pt]{% DirTh6-2-page-97.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{% DirTh6-2-page-97.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-% page-97.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-97.pdf2% svg.svg}}}+5\\|q^{0}t\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-% 2-page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-% 2-page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$	since $\\|xt\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2% svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}\leq\\|q^{0}t% \\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.% svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.% svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$ ,
	$\displaystyle=2(2(\\|st\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh% 6-2-page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh% 6-2-page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-9% 8.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.% svg}}}-\\|q^{1}t\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-% page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-% page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}% }}))+5\\|q^{1}t\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page% -98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page% -98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2% svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$	by Lemma 5 and $\\|q^{0}t\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}=\\|q^{% 1}t\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg% .svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg% .svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$ ,
	$\displaystyle=4\\|st\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2% -page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2% -page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}% }}+\\|q^{1}t\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98% .pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98% .pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$
	$\displaystyle\leq 5\\|st\\|_{\mathchoice{\includegraphics[height=6.02777pt]{% DirTh6-2-page-98.pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{% DirTh6-2-page-98.pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-% page-98.pdf2svg.svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2% svg.svg}}}$	since $\\|q^{1}t\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.% pdf2svg.svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.% svg}}{\includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}\leq\\|% st\\|_{\mathchoice{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.% svg}}{\vbox{\hbox{\includegraphics[height=6.02777pt]{DirTh6-2-page-98.pdf2svg.% svg}}}}{\includegraphics[height=4.52083pt]{DirTh6-2-page-98.pdf2svg.svg}}{% \includegraphics[height=3.01389pt]{DirTh6-2-page-98.pdf2svg.svg}}}$ .

The Spanning Ratio of the Directed 𝚯𝟔-Graph Is 5

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

2 Preliminaries

3 Lower Bound

Lemma 1.

Proof.

Claim 2.

4 Upper Bound

Theorem 3.

Lemma 4.

Proof.

Lemma 5.

Proof.

Definition 6 (Empty Region R).

Lemma 7.

Proof.

Lemma 8 (Lemma 2 in [1]).

Lemma 9 (Lemma 3 in [1]).

Lemma 10 (Lemma 4 in [1]).

Lemma 11.

Proof.

Assumption 12.

Assumption 13.

Observation 14.

Proof.

Lemma 15.

Proof.

Observation 16.

Proof.

Observation 17.

Proof.

Claim 18.

Proof.

Claim 19.

Proof.

Case Y0: 𝒗𝒚∈𝑪𝒕𝟎.

Case Y1: 𝒗𝒚∈𝑪𝒕𝟏.

Case X0: 𝒗𝒙∈𝑪𝒕𝟎.

Case X1: 𝒗𝒙∈𝑪𝒕𝟏.

Case: No such 𝒋 exists.

Case: 𝒋∈{𝟐,𝟑,𝟒,𝟓}.

References

The Spanning Ratio of the Directed $\Theta_{6}$ -Graph Is 5

Definition 6 (Empty Region $R$ ).

Case Y0: $v^{y}\in C_{t}^{0}$ .

Case Y1: $v^{y}\in C_{t}^{1}$ .

Case X0: $v^{x}\in C_{t}^{0}$ .

Case X1: $v^{x}\in C_{t}^{1}$ .

Case: No such $𝒋$ exists.

Case: $j\in\{2,3,4,5\}$ .