Paper Info
Title
Finding a Shortest Pair of Paths on the Plane with Obstacles and Crossing Areas
Abstract
Given axis-parallel rectangular obstacles and crossing areas together with two pairs of terminals on the plane, our algorithm finds a shortest pair of rectilinear paths which connect the pairs of terminals and neither pass through any obstacle nor cross each other except in the crossing areas. The algorithm takes O(n log n) time and O(n) space, where n is the total number of obstacles and crossing areas.
Year
DOI
Venue
1995
10.1007/BFb0015407
ISAAC
Keywords
Field
DocType
crossing areas,shortest pair
Obstacle,Discrete mathematics,Combinatorics,Computer science,Time complexity
Conference
ISBN
Citations 
PageRank 
3-540-60573-8
2
0.42
References 
Authors
5
3
Name
Order
Citations
PageRank
Yoshiyuki Kusakari1103.34
H. Suzuki223831.31
Takao Nishizeki31771267.08