Finding a manhattan path and related problems

Let S be a set of n horizontal and vertical segments on the plane, and let s, t ∈ S. A Manhattan path (of length k ) from s to t is an alternating sequence of horizontal and vertical segments s = r 0 , r 1 ,…, r k = t where r i intersects r i +1 , 0 ≤ i < k. An from all s ∈ S to t. Also given is a method to determine a maximum set of crossings (intersections of segments) with no two on the same segment, as well as a maximum set of nonintersecting segments, both in O ( n 3/2 log 2 log 2 n ) time. The latter algorithm is applied to decomposing, in O ( n 3/2 log 2 n ) time, a hole‐free union of n rectangles with sides parallel to the coordinate axes into the minimal number of disjoint rectangles. All the algorithms require O ( n log n ) space, and for all of them the factor log 2 n can be improved to log n log log n , at the cost of some complication of the basic data structure used.