Evading Triangles without a map
Braxton Carrigan · 2010
In this thesis we will solve the following shortest path problem. Let P be an arrangement 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 most √ 3(d+ 2 d ), 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 Toth [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.