RECTILINEAR SHORTEST PATHS AMONG OBSTACLES IN THE PLANE
Pinaki Mitra · Summit (Simon Fraser University) · 1995
T h e shortest-path problem has been studied in various settings in Computational Geometry literatures.This includes the shortest-path ~r o b l e m inside the simple polygon and the shortest-path problem avoiding a set of polygonal obstacles.Further variations of these problems are possible for different types of polygons or polygonal obstacles.In this thesis we will study the rectilinear shortest path problem avoiding a set of isothetic rectangles and vertical line segment obstacles.We will present efficient preprocessing algorithms to answer the shortest path between two arbitrary query p i n t s .We also demonstrate an approximation algorithm with less preprocessing and query time t o report an approximate shortest path between two arbitrary query points.Then we present an efficient parallel algorithm t o preprocess the set of rectangles to answer the shortest-path query between two arbitrary points using a single processor.We also present an efficient parallel algorithm t o answer the single shot shortestdistance between a source and a destination point specified during the input.Lastly we present an efficient parallel algorithm t o preprocess a set of vertical line segments t o answer the approximate shortest-path query between two arbitrary points.