Obstacle-Avoiding Path Existence Queries in a Simple Polygon

It appears your Web browser is not configured to display PDF files. Download adobe Acrobat or click here to download the PDF file.

Click here to download the PDF file.


Eastman, Matthew




A fundamental problem in computational geometry is determining whether it is possible to travel between two points in the plane while avoiding a set of obstacles. If the obstacles are known in advance, they can be preprocessed so that path-existence queries can be performed efficiently.

In this thesis, we consider a variation of the path-existence query problem where each query contains an additional set of obstacles that must be avoided. We show how to preprocess a simple polygon so that given a source and a destination within that polygon, as well as a set of pairwise disjoint convex
polygon or disk obstacles, we can efficiently determine whether there is an obstacle-avoiding path between the source and the destination.


Computer Science




Carleton University

Thesis Degree Name: 

Master of Computer Science: 

Thesis Degree Level: 


Thesis Degree Discipline: 

Computer Science

Parent Collection: 

Theses and Dissertations

Items in CURVE are protected by copyright, with all rights reserved, unless otherwise indicated. They are made available with permission from the author(s).