Finding a manhattan path and related problems

✍ Scribed by Witold Lipski Jr.

• Book ID: 102959260
• Publisher: John Wiley and Sons
• Year: 1983
• Tongue: English
• Weight: 599 KB
• Volume: 13
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.3230130308

✦ Synopsis

Let S be a set of n horizontal and vertical segments on the plane, and let s, t E S. A Manhattan path (of length k ) from s to t is an alternating sequence of horizontal and vertical segments s = ro, rl, . . . , rk = t where ri intersects ri+, , 0 < i < k . An from all s ES to r. 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(n3j2 log2 n) time. The latter algorithm is applied to decomposing, in O(n3I2 log2 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 log2 n can be improved to log n log log n, at the cost of some complication of the basic data structure used.