A shortest pair of paths on the plane with obstacles and crossing areas

Given obstacles and crossing areas together with two pairs of terminals on the plane, our algorithm finds a pair of rectilinear paths which connect th e pairs of terminals, neither pass through any obstacle nor cross each othe r except in the crossing areas, and minimize the total length, where all ob stacles and crossing areas are assumed to be axis-parallel rectangles. The algorithm takes O(n log n) time and O(n) space, where n is the total number of obstacles and crossing areas.