Obstacle-Avoiding Path Existence Queries in a Simple Polygon
Public Deposited- Resource Type
- Creator
- Abstract
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.
- Subject
- Language
- Publisher
- Thesis Degree Level
- Thesis Degree Name
- Thesis Degree Discipline
- Identifier
- Rights Notes
Copyright © 2014 the author(s). Theses may be used for non-commercial research, educational, or related academic purposes only. Such uses include personal study, research, scholarship, and teaching. Theses may only be shared by linking to Carleton University Institutional Repository and no part may be used without proper attribution to the author. No part may be used for commercial purposes directly or indirectly via a for-profit platform; no adaptation or derivative works are permitted without consent from the copyright owner.
- Date Created
- 2014
Relations
- In Collection:
Items
Thumbnail | Title | Date Uploaded | Visibility | Actions |
---|---|---|---|---|
eastman-obstacleavoidingpathexistencequeriesinasimple.pdf | 2023-05-04 | Public | Download |