Visibility graphs and motion planning

Motion planning in the presence of obstacles deals with finding efficient paths from source to target which avoid hitting any of the obstacles. Applications include motion planning in robotics and designing efficient routing systems.Theoretical concepts from graph theory, topology, and computational geometry form the basis for some of the algorithms used in motion planning. The visibility graph is a standard model used in the study of motion planning.This thesis is a report of the research project undertaken to study visibility graphs and their applications to motion planning for certain geometric objects: polygons, line segments and points.The thesis consists of two parts.Theory: This part contains the details of topics from graph theory, topology, and computational geometry in motion planning. It also includes new algorithms which were developed as a part of this thesis.Implementation: This part describes a software system to implement the theory as an example of real applications. This software also includes many tools which help in studying visibility graphs.