Planning a purely translational motion for a convex object in two-dimensional space using generalized Voronoi diagrams

AnO(n logn) algorithm for planning a purely translational motion for a simple convex object amidst polygonal barriers in two-dimensional space is given. The algorithm is based on a new generalization of Voronoi diagrams (similar to that proposed by Chew and Drysdale 1] and by Fortune 2]), and adapts and uses a recent technique of Yap for the efficient construction of these diagrams.Work on this paper by the second author has been supported in part by a grant from the U.S.-Israeli Binational Science Foundation.