Motion Planning and Visibility Problems using the Polar Diagram

Abstract

Motion planning and visibility problems are some of the most important topics studied in Computer Graphics, Computational Geometry and Robotics. There exits several and important results to these problems. We propose a new approach in this paper using a preprocessing in the plane, the polar diagram. The polar diagram can be considered as a plane tessellation with similar characteristics to the Voronoi Diagram. The Euclidean distance criterion is changed by the minimal angle criterion in this new approach. The advantage of using polar diagrams is an optimal computing preprocessing time and their immediate applications to angle problems as visibility or motion planning problems.