xy-Monotone Path Existence Queries in a Rectilinear Environment.
Gregory Bint, Anil Maheshwari, Michiel Smid · Canadian Conference on Computational Geometry · 2012
Given a planar environment consisting of n disjoint axisaligned 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 algorithms which translate the geometric problem into a tree traversal problem and present a corresponding tree structure that gives usO(n log n) construction time, O(n) space, and O(log n) query time.