Evading Triangles without a Map
by
Braxton Carrigan
A thesis submitted to the Graduate Faculty of
Auburn University
in partial ful llment of the
requirements for the Degree of
Master of Science
Auburn, Alabama
May 14, 2010
Keywords: shortest path, permeability, evading
Copyright 2010 by Braxton Carrigan
Approved by
Andras Bezdek, Chair, Professor of Mathematics
Wlodzimierz Kuperberg, Professor of Mathematics
Chris Rodger, Professor of Mathematics
George Flowers, Acting Dean of Graduate School
Abstract
In this thesis we will solve the following shortest path problem. Let P be an arrange-
ment of equilateral non-overlapping translated triangles in the plane and two points S and
T so that the segment ST is parallel to a side of each of the triangles. Assume one needs to
navigate from point S to point T by evading the triangular obstacles without any previous
knowledge of the location of the obstacles. The navigator becomes aware of a triangle once
it is contacted along the path. We will give an algorithm which enables the navigator to
reach the target point T by a path of length at mostp3(d+ 2d), where d is the length of ST.
Section 4 contains the proof, which is preceded by three sections reviewing some of the
main results and methods of previously considered shortest path problems. In particular we
will outline three papers concerning shortest path problems. First we will address the idea of
permeability of a layer mentioned by J. Pach [2] in \On the Permeability Problem" using an
integration technique. Then, we will show an improvement of permeability by G. Fejes T oth
[4] in his paper entitled "Evading Convex Discs" via existence of a path using the sweeping of
a direction technique. Finally we will outline Chapter 3 of "Shortest Paths without a Map"
by Papadimitriou and Yannakakis [3], where they show three simple heuristics of evading
rectangles.
ii
Acknowledgments
I would like to thank my advisor, Dr. Bezdek, for his academic guidance. Without his
leadership, I would not have been able to come about this conclusion or culminate it into
the written thesis.
I also would like to extend my gratitude to the members of my committee: Dr. Wlodz-
imierz Kuperberg and Dr. Chris Rodger for their time and suggestions on improving my
work. Working with them in and out of the classroom has truly been a pleasure.
I also would like to extend an appreciation to my parents Wanda and Ralph and my
wife Catie. Throughout my life all three have been a source of strength, support, and en-
couragement which has enabled me to pursue my dreams.
iii
Table of Contents
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
List of Illustrations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Background Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3 Problem and Heuristic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4 Proof of Theorem 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5 Lower Bound for any Heuristic and Open Problems . . . . . . . . . . . . . . . . 25
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
iv
List of Illustrations
2.1 Path Px in rectangle R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Square Regions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3 Region 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.4 Region 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.5 Labeling Square . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.6 Multiple  paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.7 Rectangle con guration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.8  graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.1 Path from S to T . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2 Path from S to T . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.1  1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.2 Case 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.3 Case 2-A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.4 Maximizing Case 2-A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.5 Case 2-B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
v
4.6 Maximizing Case 2-B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.7 Case 3 - A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.8 Maximizing Case 3 - A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.9 Case 3 - B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.10 Maximizing Case 3 - B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.1 Path through densest packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.2 Layers between S and T . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5.3 Navigating a Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
vi
Chapter 1
Introduction
The idea of evading convex discs was  rst addressed in the late 1960?s by L. Fejes T oth.
By the 1980?s, the topic of evading convex discs was being studied by mathematicians in
a new mathematical  eld called computational geometry. Numerous publications centered
around the idea of evading convex shapes in the plane.
The title \evading triangles without a map" refers to navigating through a plane to-
ward a target point while evading unknown triangular obstacles. To visualize this problem,
imagine walking through a thick forest with a compass and knowing in what direction and
how far to travel. To restrict this forest we will assume there are mountains that are each
translates of other, have bases of equilateral triangles, and are impassable. Finally we will
also assume that the given direction is parallel to one side of the mountains? base. While
moving the traveler cannot see through the thick forest, therefore he must rely on making
decision once encountering a mountain.
1
Chapter 2
Background Research
In the 1970?s several results were published about the notion of permeability of layers.
A layer is de ned as a parallel strip of a plane with width w containing non-overlapping
open domains called obstacles. The permeability of a layer was de ned by L. Fejes T oth to
be winf?, where ? is the length of a path from one edge of the layer to the other which evades
all open domains of the layer. J. Pach [2] in "On the Permeability Problem" proved the
following:
Theorem 2.1. (J. Pach) The permeability of any layer of squares is at most 23, and this
bound can be achieved.
Let R = x1x2x3x4 be a rectangle and  R = Siji2I be a set of non-overlapping squares
inside R (Figure 2.1). For any point x 2x1x2 we will de ne a path Px to be a path from x
to y, where y is the only point on x3x4 such that the segment xy is perpendicular to x1x2,
which evades  R. In order to evade  R for every segment uivi2xy which intersects a square
S 2 R replace uivi by the portion of the boundary between ui and vi on Si which is the
shortest; we will denote this as li(x). Let L(x) be the length of the path Px
Lemma 2.1. Rx2x1 L(x)dx 23A(R), where A(R) is the area of the rectangle R.
Proof of Lemma 2.1 will  rst show
Rx2
x1 (li(x) d(ui(x)vi(x)))dx 
A(Si)
2 .
If  i(x) denotes the length of the shortest path of the boundary of Si connecting ui(x) and
2
x1 x2
x3x4
X
Y
Px
Figure 2.1: Path Px in rectangle R
vi(x), we have
Z x2
x1
li(x) d(ui(x)vi(x))dx =
Z x2
x1
 i(x)dx A(Si)
R  
i(x)dx is evaluated in the following way
If Si has two of its sides parallel to x1x2 the act of computing is trivially 23A(R) , thus we
will assume there exist a positive angle  i between one of the sides of Si and x1x2 (Figure
2.1). We can also pick a side of Si so that 0 <  i <  4 . Now we will label the vertices s1,
s2, s3, and s4 moving left to right with respect to x1x2. We will de ne the side length of
Si to be di. We will now split Si into three regions R1, R2, and R3 by constructing lines
perpendicular to x1x2 through each of the vertices of Si (Figure 2.2). For each region we will
consider the leftmost vertical line to be it?s y-axis and de ne ri to be the interval spanned
horizontally by region Ri.
3
?
s1
s2
s3
s4
R1
R2
R3
di
r1 r2 r3
Figure 2.2: Square Regions
We will compute R  i(x)dx as Rr1  i(x)dx + Rr2  i(x)dx + Rr3  i(x)dx.
Now by symmetry R1 = R3, thus we need only compute for R1 and R2.
 i = xdi sin( i)(di +di tan( i)) inside R1.(Figure 2.3)
Since the horizontal distance of the region isdi sin( i) we calculateRr1  i(x)dxasRdi sin( i)0 xdi sin( i)(di+
di tan( i))dx = x2(di+di tan( i))2(di sin( i)) jdi sin( i)0 = (di sin( i))(di+di tan( i))2 .
?
S1
S2
S3
S4di
disin(?i)
ditan(?i)
R1
Figure 2.3: Region 1
Now for R2 we calculate the integral over half of the region since it is symmetric. Therefore
4
for the left half of the interval r2, (Figure 2.4)
 i = 2di 2( xcos( i)) with the width of r2 = dip2 cos( 4 + i).
So Rr2  i(x)dx = 2R
dip2cos( 4 + i)
2
0 2di 2(
x
cos( i))dx = 2(2dix 
x2
cos( i)j
dip2cos( 4 + i)
20 ) =
dip2 cos( 4 + i)(di di
p2 cos( 
4 + i)
4 cos( i) )
?
S1
S2
S3
S4
di?2cos(pi4 +?i)
x
Figure 2.4: Region 2
Now by adding the two previous results we get the left half of Si and by symmetry we mul-
tiply this sum by 2. Therefore R  i(x)dx = di sin( i)(di +di tan( i) +dip2 cos( 4 + i)(2di 
dip2 cos( 4 + i)
2 cos( i) =
3
2d
2
i
1+2 cos2( i)
3 cos( i)  
3
2A(Si).
Therefore Rx2x1 li(x) d(ui(x)vi(x))dx = R  i(x)dx A(Si) 32A(Si) A(Si) = A(Si)2
Thus Rx2x1 li(x)dx = Rx2x1 li(x) d(ui(x)vi(x))+d(ui(x)vi(x))dx = Rx2x1 li(x) d(ui(x)vi(x))dx+
Rx2
x1 d(ui(x)vi(x))dx 
A(Si)
2 +A(Si) =
3A(Si)
2 .
The bound is achieved when  R  lls the layer (a tiling), thus L(x) is just the sum of all li(x)
which produces the bound of 32.
G. Fejes T oth [4] improved this bound in his paper entitled "Evading Convex Discs".
5
Theorem 2.2. (G. Fejes T oth) Given a set of disjoint open squares with side-lengths not
exceeding 1, any two points of the plane lying outside the squares at distance q from one
another can be connected by a path evading the squares and having length at most 3q+12 .
We let  be the set of open squares of side-length at most 1, as in the previous theorem.
For labeling purposes we assume X is on the side X1X2. We de ne  (XY) to be the shortest
path on the boundary of S from X to a point Y on S. Also de ne  d(XY) =  (XY) to be
the distance gained by the vector   !XY in direction d. We de ne the path  (P;d) to be an
in nite path emanating from P in direction d.  (P;d) =  is constructed by  rst traveling
on a ray  !R in direction of d, then when contacting a square S 2 , evade S by traveling
along the boundary of S from X to Xi such that  (XXi) (XXi) is maximum, and then continue in
the direction of d from point Xi. Notice that  (P;d) is not uniquely determined whenever
for some S2 there exist more than one point Xi at which  (XXi) (XXi) is maximum.
Now for some point X on  we de ne l(x) to be the length of the arc of  between P and
X. To prove Theorem 2.2,  rst show
l(x) 32( (PX) + 1)
To do so we need the following:
Lemma 2.2. Let X be a boundary point on the square S = X1X2X3X4 with side length 1,
such that the ray emanating from X in the direction d intersects S, then we have:
max
1 i 4
 (XXi)
 (XXi)  
2
3
Proof of Lemma 2.2
For orientation purposes we assume that d is vertical and oriented downward. Also we
can assume that  contacts S between X1 and X2. Since the case where the side X1X2 is
perpendicular to d is trivial, we can also by symmetry assume that X1 is the vertex which
6
is vertically the highest. Now de ne a =  (X1X2) and b =  (X1X4) (Figure 2.5). Obviously
a2 +b2 = 1.
X1
X2
X3
X4
d
X a
b
Figure 2.5: Labeling Square
Now we consider two cases
Case 1: a  b
In this case a 
p2
2 , therefore
 (XX2)
 (XX2) = a 
p2
2 >
2
3
Case 2: 0 <a<
p2
2 <b< 1
In this case we show that either traveling to X3 or X4 produces    23.
Notice that  (X1X4) (X1X4) = b > 23 and  (X2X4) (X2X4) = b a2 < 12 < 23.
Also notice that as X moves from X1 to X2 the ratio  (XX4) (XX4) decreases, therefore there exists
some point X0 between X1 and X2 where  (X0X4) (X0X4) = 23. Obviously if X 2 X0X1, then
 (XX4)
 (XX4)  
2
3.
Now we assume X2X0X2 and show that  (XX3) (XX3) > 23.
First notice that  (XX3) (XX3) increases as X approaches X2, therefore it su ces to show that
 (X0X3)
 (X0X3)  
2
3.
We denote the distance from X0 to X1 by x therefore producing:
 (X0X3) = a+b ax with  (X0X3) = 2 x,
7
 (X0X4) = b ax with  (X0X4) = 1 +x.
Since  (X0X4) (X0X4) = 23 = b ax1+x , we have 2(1 + x) = 3(b - ax)
We want to show that 2(2 x) < 3(a+b ax). Since b> 0 this is equivalent to 3a2 4a+1 < 0,
which is indeed true for
p2
2 <a< 1. Therefore we have shown Lemma 2.2 to be true.
Now returning to Theorem 2.2, if we begin  at a point P and end at a point X of  which
does not lie on a boundary of some S2 , then it is obvious that:
(1)
l(X) 32 (PX)
Thus we will look at the case where X lies on a boundary of a square which  evades. We
will denote this square by Si and let the  rst point where  contacts it be Vi and the last
point where  contacts Si be Wi. Since l(Vi) 32 (PVi), It is su cient to prove the bound
for l(X) l(Vi)
We have two cases to consider.
Case 1: X and Wi lie on the same side of Si
Notice XWi 1, therefore:
(2)
l(X) l(Vi) = l(Wi) l(Vi) XWi 32 (ViWi)  (XWi) =
3
2( (ViWi)  (XWi)) +
1
2 (XWi) 
3
2 (ViX) +
1
2
Case 2: X and Vi lie on the same side of Si
In this case notice that 32 (ViX) + 12 + l(Vi) l(X) is a linear function of x. Thus it is
8
enough to show that the endpoints satisfy the bound. If X is in fact a vertex of S, then this
expression is positive, and if X = Vi, then as seen above this expression is 12. Thus we know
that for any point X on the path  , l(X) 32( (PX) + 1).
Now for two points A and B we need to show that there exists a path  emanating from
point A, travels through point B, and has a length of at most 3q+12 .
If there exist some direction d such that  A;d passes through B, then the above lemma shows
existence. Therefore we shall assume there is no such direction.
d
B
A
M1
M2 l
Figure 2.6: Multiple  paths
For every direction d we de ne a line l perpendicular to d passing through point B. As
previously mentioned  P;d is not uniquely determined, thus we will label the intersection of
 A;d and l by mi, for i 2 I and order I from left to right on l. Consider d to be nearly
perpendicular to AB pointing to the right and slightly downward; for such a d it is obvious
9
that mi is to the left of B. Similarly if d is to the left and slightly downward, mi to the right
of B. Now we sweep the direction d. Notice as we sweep d, if between two such directions  
is uniquely determined, then mi is continuous along l. Now if for d, there exist two vertices
which satisfy Lemma 2.2, then we have two points which intersect l; one is the right most
point of a continuous interval of l and the other is the left most point of a continuous interval
of l. Since there is no d such that B2 A;d, then there must be some direction which has
points mi and mj separated by B (Figure 2.6). We will consider this direction.
Now we will look at direction d and  B; d noticing that this path must intersect one of the
paths  A;d. Let the  rst point where  B; d intersect  A;dbe Z. Now Z will be on a boundary
point of some Si 2 . Thus by inequality (1) we know either  A;d or  B; d is at most 32 
and the other by (2) is at most 32 + 12. Now obviously   d(BZ) =  d(ZB) thus it follows
that when connecting the appropriate  from A and B respectively there exists a path PA;d
containing point B such that l(B) 32AB + 12.
Also G. Fejes T oth uses a similar argument to show:
Theorem 2.3. Given a set of disjoint open unit circles, any two points of the plane lying
outside the circles at distance d from one another can be connected by a path evading the
circles and having length at most 2 p27(d 2) + 
Papadimitiou and Yannakakis [3] published "Shortest Paths without a Map" in Novem-
ber 1988, which is considered the  rst paper on this subject written by those working in the
new  eld called "computational geometry". They introduce the concept of moving through
the plane toward a target point while evading unknown obstacles in the section entitled "Ob-
stacle Scenes". It seems natural to compare the algorithmic path to the shortest existing
path, and show a bound for the ratio of their lengths. Surprisingly, in the case when the
obstacles are rectangles with one side parallel to the segment having endpoints of the start
(S) and target (T) such bound does not exist.
10
Theorem 2.4. (Papadimitiou and Yannakakis) In the case of parallel rectangles there is no
upper bound for the ratio of the algorithmic path to the shortest path.
We prove Theorem 2.4 by constructing a con guration of rectangles which forces the
ratio to be at least  (n2)
 (n32 )
. We say that the path has order n, denoted by  (n), if the ratio
is determined by some constant multiplied with n. In the construction, the start and target
points are distance n apart. The con guration will consist of n rectangles each of which have
a horizontal side length of  and a vertical side length of n. The position of the rectangles
will be revealed as we challenge the given algorithm. First we place a rectangle such that
n
2 of the length of the rectangle is above the current position of the traveler and
n
2 is below
(Figure 2.7). Now continue this with n rectangles at each point where the traveler crosses
the last vertical line shared which has a common point with the previously evaded obstacle.
Thus the vertical distance traveled is at least n2 for each of the rectangles and obviously a
horizontal distance of n covered by the entire path, thus the path for the given algorithm is
at least n22 + n, thus being  (n2), and therefore the ratio of this path to the shortest path
as n goes to in nity exceeds any constant bound.
Now the shortest path is found noticing that there exist a horizontal line at a distance  
npn from the segment ST which contacts less thanpn rectangles. For contradiction assume
this line does not exist, thus assuming every line from npn above or below the segment ST
contacts at least n rectangles. Conversely, if all lines within npn contact at leastpn rectan-
gles, then sweeping a line from bottom to top of our range and integrating the total length
of the common points of the horizontal line with the rectangles we conclude that the area
covered by the intersection of all the lines and the rectangles is 2n2 . Since there are exactly
n rectangles of length n and width  , then there is exactly n2 area covered by the rectangles.
Therefore there exists a horizontal line that contacts less thanpn rectangles, so we will use
this line to traverse the layer by using the simple evade and return technique. Therefore
traversing the layer on this line, with the evade and return heuristic, will have no more
11
S T
Figure 2.7: Rectangle con guration
than npn vertical distance and the distance of this line from ST is no more than npn. So
there exists a path from S to T that has a length of less than 3npn, thus being  (n32 ).
The paper also addresses the issue of the obstacles being squares.
De nition 2.1. The ratio of a given algorithm is de ned ratio of the longest path created by
the algorithm evading any con guration of obstacles in the plane to the length of the segment
ST where s is the starting point and T is the target point of the path.
Theorem 2.5. No algorithm for evading square obstacles in a plane can produce a ratio
better than 32.
To prove Theorem 2.5, following the exact same construction as before, an algorithm
can produce a path length no shorter than  (32n). On the other hand, the same integration
method shows a path of length  (n), thus algorithms cannot produces a ratio better than
12
3
2.
Finally Papadimitiou and Yannakakis give a heuristic that produces a ratio arbitrarily
close to 32 as n grows. The heuristic involves a bias which determines the direction the trav-
eler evades a square. The heuristic allows for the path to evade a square by always choosing
the corner of the square closest to segment ST provided it is no farther than 12 +  , where
 is the bias, otherwise evade the square by going to the other corner. To determine the
bias we will  rst de ne  = 1pn for n the length of ST, then begin with  =  . Now while
moving through the plane, if the path requires you to move farther from ST then increase
 by adding  , but if you move closer to the segment ST, then decrease  by subtracting  .
In the heuristic it is obvious that  is never larger than 12 therefore we never travel a
vertical distance farther than 12 =  (pn) from the segment ST. Thus the only concern is
when the path requires a vertical travel of more than 12 to evade a square. In this case we
notice that we never travel farther than 12 + . Figure 2.8 is a possible graph of  .
epsilon1
+epsilon1 -epsilon1
Bias?
numberofsquarescontacted
Figure 2.8:  graph
Notice that whenever the heuristic requires a travel of length greater than 12 the value of
 decreases. Now whenever this occurs there exists some evasion earlier, where  had been
13
increased to the current value, therefore the vertical travel is equalized up to  throughout
the path. Since n  = pn therefore as n grows, the heuristic produces a ratio arbitrarily
close to 32. .
14
Chapter 3
Problem and Heuristic
Many di erent shortest path problems can be formulated by simply changing the ob-
stacles in the plane. The problem solved in this section was motivated by the results of A.
Bezdek [1]. Our solution itself does not use the method of this paper, and we believe the
result to be new. In this section we will solve the following:
Problem: We will assume we wish to traverse a plane toward a target point T from a
starting point S while avoiding equilateral triangles of unit side length. The obstacles will
be assumed to be non-overlapping translates with one side parallel to the segment ST and
will be unknown until we come in contact with the triangle. Our goal is to create a heuristic
which enables us to reach our target point along a path P that is shorter than the trivial
path that is twice the length of the segment ST.
The trivial Heuristic of evading each triangle returning to ST by following the boundary
of the triangle obviously produces an upper bound of 2 (Figure 3.1).
S T
Figure 3.1: Path from S to T
A lower bound can be seen by the permeability of a layer discussed in Section 5 to be
1+p3
2 .
15
Triangle Heuristic: When navigating through the plane toward the target point T,
follow the steps below. (For a better visual understanding we included Figure 3.2 of a con-
crete path created by this heuristic.
0. Start at S.
1. Travel along segment ST toward T.
If T is reached, then go to 6.
Else, next.
2. Travel along an edge of the contacted triangle toward the vertex not on the side
parallel to the segment ST.
If you cross a line E forming a 30o angle with ST passing through T, then go to 5.
Else, next.
3. Take a 90o turn toward T and travel on line L toward the segment ST.
4. Travel along line L.
a. If you reach ST, repeat 1.
b. Else, If you contact a triangle which overlaps the segment ST, repeat 2.
c. Else, If the contacted triangle does not overlap the segment ST, then travel
on the shortest path along the edges of the triangle back to line E
and repeat 4.
5. Travel on line E toward T.
If a triangle is contacted, avoid the triangular obstacle in the shortest path
returning to line E and repeat 5.
Else, T is reached, then go to 6.
6. Stop.
16
Theorem 3.1. If the Triangle Heuristic is followed throughout the plane, then the ratio of the
length of the path P to the length of the segment ST is smaller thanp3(1+ 2n2 ) 1:732(1+ 2n2 ),
where n is the length of the segment ST.
S T
Step 1
Step 2
Step 3
Step 4c
Step 4b
Step 5
line E
Step 6Step 4a
Figure 3.2: Path from S to T
17
Chapter 4
Proof of Theorem 3.1
For orientation purposes we assume that the segment ST is horizontal and all triangles
point upward, meaning the side parallel to ST in each triangle is below the third vertex.We
also use the same notation as introduced in section 3.
P TST is a collection of disjoint segments aibi;i = 1;:::;k. Let S = a1 and assume the
segments are labeled according to their order on ST. We consider the subarcs  i 2P ST,
where  i is the portion of P from bi to ai+1. Through the proof of Theorem 3.1 we refer to  
as one of these subarcs. Let L be the length of  and let D be the length of the segment
biai+1. We will show that L D
 
<p3 for each  of P.
A detailed analysis of the Triangle Heuristic reveals that there are only four di erent types
of subarcs,  , to consider:
Case 1: Subarc produced by three consecutive steps: 2 else, 3, 4a.
Case 2: Subarc produced by three consecutive steps: 2 else, 3, 4b.
Case 3: Subarc produced by three consecutive steps: 2 else, 3, 4c.
Case 4: Subarc produced by two consecutive steps: 2 if, 5.
Notice that each subarc begins by traveling to the vertex not on the side parallel to ST. We
will assign the variable t to the length between bi and the before mentioned vertex. Then
each time the heuristic requires a 90o turn toward T (Figure 4.1).
S T
b1
t
?1
Figure 4.1:  1
18
Now we examine each of the four types of subarcs by its direction through the triangle
heuristic starting at step 2.
Case 1: Subarc produced by three consecutive steps: 2 else, 3, 4a.
We return to the segment ST without contacting another triangle(Figure 4.2).
Thus  forms the legs of a right triangle with biai+1 the hypotenuse of this triangle.
S T
?
Right Triangle
bi ai+1
Figure 4.2: Case 1
Since the obstacles are equilateral triangle translates, this right triangle has two angles being
60 and 30 degrees respectively. Thus it is obvious that the ratio of L D
 
is 2+
p3
4  1:366.
Case 2: Subarc produced by three consecutive steps: 2 else, 3, 4b.
We contact a second triangle which overlaps the segment ST.
In this case we let  have an end point where the path reaches this second triangle; the
next  will begin there. Note that starting a  on the edge of the triangle only reduces the
ratio since the edge of the triangle is in a ratio of 2:1 with respect to L D
 
. We distinguish
two subcases depending on the position of the second triangle. Thus the next  can be
considered as one of our 3 types of subarcs.
Part A: The  rst triangle contacted by  is above the second triangle contacted (Fig-
ure 4.3).
19
S T
?
bi ai+1
Triangle which is below the first triangle contacted
End of consideration of ?
Figure 4.3: Case 2-A
The greatest ratio is found when the two triangles are touching (Figure 4.4). Here we
 nd that the ratio of L D
 
is equal to t+
p3
2
(t2+34) which is maximized as t approaches 1, producing
a ratio approximately equal to 1.4928, being smaller than the needed bound.
S T
end of consideration of ?
t
t
2 +
3
4
?3
2
bi
Edge of triangle obstacle
Figure 4.4: Maximizing Case 2-A
Part B: The  rst triangle contacted by  is below the second triangle contacted (Figure
4.5).
Again it is obvious that the maximum ratio occurs when the two triangles are touching.
It is also easy to see that the ratio increases as the second triangle slides along the  rst
one so that its base gets closer to ST. Indeed, when the second triangle moves toward the
20
S T
?
bi ai+1
Triangle which is above the first triangle contacted
End of consideration of ?
Figure 4.5: Case 2-B
segment ST along the edge of the  rst triangle the part of  which is not following the side
of the  rst triangle decreases. This is signi cant since the portion of  which is following the
side of the  rst triangles travels with a ratio of 2:1 with respect to L D
 
whereas the second
part of  travels with a ratio of p3:1 with respect to L D
 
. Therefore as the second part of  
decreases, the ratio of L D
 
increases. Thus the position of the triangles which maximizes the
ratio of  D
 
is as in Figure 4.6.
S T
End of con-
sideration of
?
t
t?3
2
t
t
4
bi ai+1
Figure 4.6: Maximizing Case 2-B
Now L D
 
= t+
p3t
2
t+t4 =
4+2p3
5  1:493 <
p3.
Case 3: Subarc produced by three consecutive steps: 2 else, 3, 4c.
We contact a triangle which does not overlap the segment ST (Figure 4.7).
Part A: We either repeat step 4 as 4a or 4c. As in the heuristic, we will avoid the
21
S T
?
ai
bi+1
Figure 4.7: Case 3 - A
triangle by following its perimeter in the shortest direction back to ST. By the assumptions
of the triangles the con guration that maximizes L D
 
is when the second triangle?s perimeter
and  have the longest part, i.e. when the second triangle is contacting the  rst triangle
on the segment ST. Therefore the con guration which maximizes L D approaches the same
con guration as in Case 2 - Part B. Since the triangle is strictly above ST, then  ends once
it has completely evaded the second triangle (Figure 4.8).
We will also make the observation that only two triangles that do not overlap the seg-
ment ST can be in contact with any particular  . In this case the detours caused by two
triangles are shorter than the one which can be generated by one triangle.
The ratio associated with the extreme case depicted on Figure 4.8 is L D
 
= 3+2
p3
2+p3 =
p3.
S T
?
bi
ai+ 1
Figure 4.8: Maximizing Case 3 - A
Part B: We repeat step 4 as 4b.
We then contact a triangle which does overlap the segment ST(Figure 4.9).
Notice that the triangle which overlaps the segment ST must be below the  rst trian-
gle contacted as in Case 2 - Part A. Otherwise the middle triangle cannot be involved in  .
Therefore this case is similar to the one shown on Figure 4.9.
22
S T
?
bi ai+1
Figure 4.9: Case 3 - B
Now we  nd the con guration which maximizes L D
 
. Just as in Case 3 we can assume
that the triangle which does not overlap segment ST is touching the  rst triangle of  . Also
without loss of generality, we can assume the triangle overlapping segment ST is touching
the before mentioned triangle or as in Case 3 it could be moved downward to be in contact.
For now we calculate L D
 
as if  ends when it contacts the triangle which overlaps ST as
in Case 3. Finally, notice that as we lower both of these triangles while keeping them in
contact, D stays the same and obviously as in Case 3 the length of  increases thus the
maximum con guration is as in Figure 4.10.
S T
?
bi ai+1
End of consideration of ?
Figure 4.10: Maximizing Case 3 - B
Now for such a  , L D
 
depends on t. As seen above  D
 
is 4t+3+
p3
2t+3 = 2 +
 3+p3
2t+3 which is
obviously maximized when t = 1, thus  7+
p3
5  1:7564.
Currently this case can produce a ratio larger than the claim ofp3 but if we have such
a  we will have limitation on the remaining portion of  . Therefore, we will now show that
23
these two consecutive portions produce a L D
 
that is smaller than p3. So for this situation
we will have the  rst  maximum value as 4t + 3 +p3, then we will look at the second  .
As the  rst  increases it approaches the restriction that the second  has a length t which
approaches 0. Thus whichever con guration the second portion of  must navigate, it no
longer includes a large portion that follows the edge of a triangle having a ratio of 2:1 with
respect to L D
 
. Without calculation we can see that all other portions of any possible  are
signi cantly smaller than the ratio of the theorem because all cases include the edge having
a ratio of 2:1, but when all parts of  are calculated the total of L D
 
is smaller than the ratio
of the theorem.
Case 4: Subarc produced by two consecutive steps: 2 if, 5.
We reach the line E which forms a 30o angle with ST passing through T. This is the only
place where the triangle heuristic does not guarantee to produce L D
 
smaller than the claim.
This occurs when a triangle is placed closely in front of the target point requiring the path
P to evade this triangle by a  which follows two edges of the triangle, thus L D
 
approaches
2. Thus as ST gets larger this  will have less of an impact on the overall ratio of L to D 
contributes the additional 2n term to the bound.
24
Chapter 5
Lower Bound for any Heuristic and Open Problems
A lower bound for the problem given in Section 3 is easily seen to be 43 by computing the
path through the densest packing of equilateral triangular translates. If ST passes through
the side of a triangle then it is easy to see that the shortest path is 43d, where d is the length
of ST (Figure 5.1), yet we will use the technique from Section 2 to improve this lower bound.
S T
12 12
12 121
2
Figure 5.1: Path through densest packing
Theorem 5.1. 1+
p3
2 is a lower bound for traversing a plane while evading triangular obsta-
cles.
We will challenge a heuristic by placing triangles once the navigator has reached a line
extending 60o from ST, in a way similar to the technique used by Papadimitriou and Yan-
nakakis [3]. First let S = S1,then extend a line Li, forming 60o with ST through point Si.
Now place an equilateral triangle which shares a side with Li such that Si is the midpoint
25
of this side. Now the triangle that has been placed will determine a layer between Li and
Li+1. The vertex which is not on line Li will now de ne a line Li+1 which goes through this
vertex and forms a 60o angle with ST. Now the path created by any heuristic must intersect
this line, thus consider the intersection point of the path and Li+1 to be Si+1 and repeat this
process of placing triangles. Since the size of the triangles can be determined as necessary,
we can form a series of layers, in this fashion, which connect S to T (Figure 5.2). For each
S T
L1 L2 L3 L4 L5 L6
Figure 5.2: Layers between S and T
layer we will show that, with the triangle placed in this manor, the navigator will travel in
a ratio of 1+
p3
2 to the distance traveled with respect to the ST. We can assume the triangle
has side length 1 thus forcing the navigator to travel a length of at least 12 +
p3
2 to traverse
the layer, and the length of ST T the layer is 1 (Figure 5.3).
12
?3
2
S T
Figure 5.3: Navigating a Layer
26
Open Problems:
From the results of Theorem 3.1 it seems natural to investigate the possibility of changing
the restraints of the obstacles. Such changes involve allowing one or more of the following:
1. The triangular obstacles need not be of the same side length.
2. The triangular obstacles can be of any orientation in the plane.
3. The triangular obstacles need not be equilateral.
From the conclusion of these variations it might be possible to generalize the results in
order to traverse 3-space with obstacles being regular tetrahedra.
27
Bibliography
[1] A. Bezdek, Evading cubes in the three space, Beitr age zurn Algebra und Geometrie,
40, (1), (1999), 105-111.
[2] J. Pach, On the permeability problem, Studia Scientiarum Mathematicarum Hungarica
12, (1977), 419-424.
[3] C. H. Papadimitriou and M. Yannakakis, Shortest paths without a map, Proc. 16th In-
ternat. Colloq. on Automata, Languages, and Programming, Lecture Notes in Computer
Science Vol. 372, Springer-Verlag (1989), 610-620.
[4] G. F. T oth, Evading Convex Discs, Studia Scientiarum Mathematicarum Hungarica 13,
(1978), 453-461.
28