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.

Additional Metadata
Conference 24th Canadian Conference on Computational Geometry, CCCG 2012
Citation
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.