Name
Abstract | ||
|---|---|---|
Let A be a plane region which is bounded by an outer rectangle and an inner one and has r rectangular obstacles inside the region. Let k terminal pairs lie on the outer and inner rectangular boundaries. This paper presents an efficient algorithm which finds k non-crossing rectilinear paths in the plane region A, each connecting a terminal pair without passing through any obstacles, whose total length is minimum. Non-crossing paths may share common points or line segments but do not cross each other in the plane. The algorithm runs in time O(n log n) where n=r+k. |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1007/3-540-57568-5_239 | ISAAC |
Keywords | Field | DocType |
finding shortest non-crossing rectilinear,plane regions | Discrete mathematics,Line segment,Combinatorics,Computer science,Rectangle,Floyd–Warshall algorithm,Yen's algorithm,Shortest Path Faster Algorithm,Time complexity,Planar graph,K shortest path routing | Conference |
ISBN | Citations | PageRank |
3-540-57568-5 | 8 | 0.58 |
References | Authors | |
4 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jun-ya Takahashi | 1 | 80 | 9.82 |
| Hitoshi Suzuki | 2 | 10 | 2.01 |
| Takao Nishizeki | 3 | 1771 | 267.08 |