XY-Monotone path existence queries in a rectilinear environment
Given a planar environment consisting of n disjoint axis- Aligned rectangles, we want to query on any two points and find whether there is a north-east monotone path between them. We present preprocessing and query al- gorithms 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.
|Conference||24th Canadian Conference on Computational Geometry, CCCG 2012|
Bint, G. (Gregory), Maheshwari, A, & Smid, M. (2012). XY-Monotone path existence queries in a rectilinear environment. Presented at the 24th Canadian Conference on Computational Geometry, CCCG 2012.