Translational motion planning for a convex polyhedron in a 3D polyhedral world using an efficient and new roadmap
Abhi Dattasharma, S. Sathiya Keerthi · NOT FOUND REPOSITORY (Indian Institute of Science Bangalore) · 1993
We consider the problem of moving a convex polyhedral object among convex polyhedral obstacles which have pairwise disjoint interiors in three dimensional Euclidean space. We use an augmented Voronoi diagram, which is complete when the free space is bounded, and prove that the size of this diagram is in $O(n^2)$ when the size of the moving object and the number of obstacles are assumed to be constant and n is the total number of faces on the obstacles. We also give an efficient and easy to implement algorithm to construct the roadmap.