Publications [#331371] of Bruce R. Donald

Papers Published

1. Canny, J; Donald, B, Simplified voronoi diagrams, in Proc. Third ACM Symposium on Computational Geometry, Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987 (October, 1987), pp. 153-161, Waterloo, Ontario, ISBN 0897912314 [doi]
   (last updated on 2018/01/26)

   Abstract:
   © 1987 ACM. We are interested in Voronoi diagrams as a tool in robot path planning, where the search for a path in anr dimensional space may be simplified to a search on an r - 1 dimensional Voronoi diagram. We define a Voronoidiagram V based on a measure of distance which is not a true metric. This formulation has lower algebraiccomplexity than the usual definition, which is a considerable advantage in motion planning problems with manydegrees 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 half-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 usefulproperty, any path through free space which starts and ends on the diagram ran be continuously deformed so that it lies entirely on the diagram. Thus it is still complete for motion planning, but it lias lower algebraiccomplexity than a diagram based on the euclidean metric.