Minimum link paths in polygons and related problems

Abstract

Consider the motion of a robot in a two-dimensional Euclidean space that is bounded by a simple polygon. The robot can move only along straight-line segments and the boundary of the polygon represents an impenetrable obstacle. Suppose that it is easier for the robot to move in a straight line rather than to turn and rotate. In this thesis, we investigate problems related to paths of fewest number of turns (or minimum link paths), under the simplifying assumption that robot is a point. In particular, we present efficient algorithms for the following problems in a polygon P: (1) Find a minimum link path between two given points of P. (2) Find minimum link paths between a fixed point and all the vertices of P. (3) Preprocess P with respect to a fixed point x such that the number of edges in a minimum link path between x and a query point can be determined in logarithmic time. (4) Compute the link diameter of P (which is the maximum number of edges in any minimum link path of P). We also consider problems where the complexity of a path is measured by its Euclidean length rather than by its number of turns. In this geodesic metric, the distance between two points of the polygon is the length of the shortest Euclidean path between them. We present fast algorithms for the following problems in P: (1) Compute the geodesic diameter of P (which is the maximum distance between any two points of P). (2) Compute geodesic furthest neighbors for all the vertices of P (furthest neighbor of a point x is another point in P whose distance from x is maximum). Several open problems are discussed at the conclusion of the work.