Simplified Voronoi diagrams

摘要

We are interested in Voronoi diagrams as a tool in robot path planning, where the search for a path in an r dimensional space may be simplified to a search on an r - 1 dimensional Voronoi diagram. We define a Voronoi diagram V based on a measure of distance which is not a true metric. This formulation has lower algebraic complexity than the usual definition, which is a considerable advantage in motion planning problems with many degrees of freedom. In its simplest form, the measure of distance between a point and a polytope is the maximum of the distances of the point from the hMf-spaces which pass through faces of the polytope. More generally, the measure is defined in configuration spaces which represent rotation. The Voronoi diagram defined using this distance measure is no longer a strong deformation retract of free space, but it has the following useful property: any path through free space which starts and ends on the diagram can be continuously deformed so that it lies entirely on the diagram. Thus it is still complete for motion planning, but it has lower algebraic complexity than a diagram based on the euclidean metric.