Overview

In this paper we present an approximation algorithm for solving the following optimal motion planning problem: Given a planar space composed of triangular regions, each of which is associated with a positive unit weight, and two points s and t, find a path from s to t with the minimum weight, where the weight of a path is defined to be the weighted sum of the lengths of the sub-paths within each region.

Some prior algorithms (Lanthier et al. [9] and Alek-sandrov et al. [1]) took a discretization approach by introducing m Steiner points on each edge. A discrete graph is constructed by adding edges connecting Steiner points in the same triangular region and an optimal path is computed in the resulting discrete graph using Dijkstra's algorithm. To avoid high time complexity, both [9] and [1] use a subgraph of the complete graph in each triangular region. As a result, in the discrete graph only an approximate optimal path can be achieved, whose error is proportional to the weight of the optimal path. This approximate optimal path then is used to approximate the optimal path in the original problem.

Our algorithm extends these algorithms by dynamically maintaining O(m) edges in each region to compute the exact shortest path in the discrete graph efficiently. The running time of this algorithm is O(mn log mn), where n is the number of triangular regions. Our...