Computational geometry has arisen as an extremely important field of theoretical computer science and is finding applications in many other fields, such as robotics, computer-aided design, mechanics, computer graphics, operations research, and VLSI design. While the field of computational geometry is still young, many recent breakthroughs have resulted in a flurry of activity, particularly in applications to robotics. This project is designed to identify important areas of robotics to which techniques of computational geometry may be applied. It will initially focus on the design and analysis of geometric algorithms for robotics, particularly those problems related to motion planning and shortest path planning. The research builds on an existing body of work in shortest path algorithms for motion in the plane in the presence of obstacles and "weighted regions." Further research should improve the bounds on the computational complexity of a variety of fundamental problems. A better understanding of basic geometric algorithms will lead to efficient and effective heuristics for solving important problems in robotics.
