Premium
Finding a manhattan path and related problems
Author(s) -
Lipski Witold
Publication year - 1983
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230130308
Subject(s) - combinatorics , binary logarithm , disjoint sets , mathematics , path (computing) , sequence (biology) , plane (geometry) , log log plot , set (abstract data type) , space (punctuation) , discrete mathematics , geometry , computer science , biology , genetics , programming language , operating system
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.