Voronoi diagrams and algorithmic motion planning: Parallel and randomized techniques

The ability to manipulate objects in computer graphics and robotics depends critically on fast and feasible solutions to motion planning problems. The central theme of this dissertation is the effective use of parallel and randomized algorithmic techniques to obtain efficient performance bounds for planar motion planning instances. We present results that extend the applicability of these techniques to some fundamental problems in computational geometry that are central to motion planning and also have other varied applications. For instance, we present efficient parallel algorithms for the Voronoi diagram of line segments. Voronoi diagrams are elegant and versatile geometric structures with applications in a wide range of seemingly unrelated areas. We consider the fixed-connection network model of parallel computation (the mesh-connected computer) as well as the PRAM (Parallel Random Access Machine). Briefly, we demonstrate the following results. We present a linear time algorithm, on an n x n mesh, for finding the shortest-path motion of a convex object with two degrees of freedom (dofs) moving amongst convex obstacles in the plane. This is worst-case optimal. We also show that the Voronoi diagram of a set of n line segments in the plane can be constructed mesh-optimally in $O(\sqrt{n})$ time on a mesh with n processors. Consequently, we obtain an $O(\sqrt{n})$ time algorithm for the retraction method of planning motion for an object with two dofs. For many problems, randomization allows us to design algorithms that are simpler and more efficient than their deterministic counterparts. We present further evidence of the power of random sampling techniques for efficient parallel algorithm design in computational geometry. We present an optimal randomized parallel algorithm for constructing the Voronoi diagram of a set of line segments in the plane. Our PRAM algorithm runs in O(log n) time with very high probability, using $O(n)$ processors. The result is achieved by using a two-staged sampling technique. This settles the open question of an optimal parallel solution to this problem. Our algorithm also implies optimal solutions for a number of problems that can be solved efficiently from the diagram. In particular, we obtain an optimal randomized parallel algorithm for the retraction method of finding a path of motion for an object with two dofs moving in the plane