Simplified Voronoi diagrams (Q1101687)

The move of a polytope in the 3-space among obstacle polytopes can be described as a path in the configuration space \(R^ 3\times SO(3)\). The problem of finding a possible path between two points of the configuration space arises from robot path planning and is known among piano movers as well. The authors reduce the problem to a search on a Voronoi diagram in one dimension lower. The Voronoi diagrams deferred here are not based on a true metric and are no longer strong deformation retracts of the free space; however, any path through the free space which starts and ends on the diagram can be continuously deformed so that it lies entirely on the diagram, therefore, the method suggested is still complete for motion planning and has a lower algebraic complexity than a diagram based on the Euclidean metric.