Award Date


Degree Type


Degree Name

Master of Science (MS)


Computer Science

First Committee Member

Yonina Cooper

Number of Pages



Research and development work in robotics and industrial automation has prompted a need for efficient motion planning algorithms for collision avoidance. To build fully autonomous robots, these algorithms must also model the environment correctly and accurately to safely maneuver the robot around obstacles. The main focus of this thesis is on the following problem and its solution: Given a set of obstacles represented as polygons in two-dimensional space, determine the shortest, collision-free path from the source point of the robot to some destination point. A fast and efficient algorithm for solving this problem is based on a plane-sweeping technique and runs in O(N{dollar}\sp2{dollar} log N) time; Since this solution has been studied very briefly in its theoretical form by (SS84), we present an in-depth analysis of the plane-sweep algorithm along with a full-scale implementation as well as an animation of the plane-sweeping technique.


Algorithm; Construction; Graph; Path; Plane; Planning; Robot; Sweep; Visibility; Visualization

Controlled Subject

Computer science; Industrial engineering

File Format


File Size

2519.04 KB

Degree Grantor

University of Nevada, Las Vegas




If you are the rightful copyright holder of this dissertation or thesis and wish to have the full text removed from Digital Scholarship@UNLV, please submit a request to and include clear identification of the work, preferably with URL.


IN COPYRIGHT. For more information about this rights statement, please visit