Shortest paths in weighted polygons.

Abstract

Consider a polygon P and two points $p,\ q\in P.$ Suppose that to move from p to q, we can travel along the edges of P or through the interior of P. Assume that the speed at which we can travel along the edges of P is one unit per second, and the travel speed through the interior of P is 1/s units per seconds ($s>1$). The problem consists of finding the shortest path between p and q. We solve this problem in O(n) time for convex polygons. For simple polygons, we show two algorithms. The first algorithm runs in O(E log n) time using O(E) space (where E is the size of the visibility of P). The second algorithm has two variations which both require O(n E log n) preprocessing (where E is the number of edges in the visibility graph of P). The first variation takes O(n log n) query time and O($n\sp2$ log n) space. The second variation has a query time of O(n log$\sp2$ n) but uses $O(n\sp2)$ space. For the orthogonal case, we give a O(E) time and space algorithm.