Paper Info
Title
An augmented Voronoi roadmap for 3D translational motion planning for a convex polyhedron moving amidst convex polyhedral obstacles
Abstract
This paper concerns the development of a piecewise linear Voronoi roadmap for translating a convex polyhedron in a three-dimensional (3-D) polyhedral world. In general the Voronoi roadmap is incomplete for motion planning, i.e., it can have several disjoint components in one connected component of free space. An analysis of the roadmap shows that incompleteness is caused by the occurrence of the following simple geometric structure: a polygon in the Voronoi surface containing one or more polygons inside it. We formally bring out the details of this geometric structure and give an efficient augmentation of the roadmap that makes it complete. We show that the roadmap has size e = O ( n 2 Q 2 l 2 ), where n is the total number of faces on the obstacles, Q is the total number of obstacles and l is the number of faces on the moving object. We also present an algorithm to construct the roadmap in O (( n + Ql ) e + Q 2 log Q ) time.
Year
DOI
Venue
1995
10.1016/0304-3975(94)00191-K
Theor. Comput. Sci.
Keywords
DocType
Volume
translational motion planning,amidst convex polyhedral obstacle,augmented Voronoi roadmap,convex polyhedron
Journal
140
Issue
ISSN
Citations 
2
Theoretical Computer Science
6
PageRank 
References 
Authors
0.50
8
2
Name
Order
Citations
PageRank
Abhi Dattasharma1193.39
S. Sathiya Keerthi24455527.30