|
||||||
|
||||||
| Undergraduate Honours Projects | ||||||
|
Carleton University - School of Computer Science Undergraduate Honours Project Fall 2011 xy-monotone path queries in a rectilinear environment Gregory Bint 
ABSTRACT Given a planar environment containing n disjoint axis-aligned rectangles, we want to query on two points and be told whether there is a north-east monotone path between them. We present preprocessing and query algorithms which translate the geometric problem into a tree traversal problem and present a corresponding tree structure that gives us O(n log n) construction time, O(n) space, and O(log n) query time. We also review several point location query algorithms that suit the problem and which offer the reader a choice in balance between performance and implementation complexity. |
||||||
|
