Computing homotopic shortest paths efficiently

被引：0

作者：

Efrat, A ^{[1
]}

Kobourov, SG

Lubiw, A

机构：

[1] Univ Arizona, Dept Comp Sci, Tucson, AZ 85721 USA

[2] Univ Waterloo, Sch Comp Sci, Waterloo, ON N2L 3G1, Canada

来源：

ALGORITHMS-ESA 2002, PROCEEDINGS | 2002年 / 2461卷

关键词：

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

We give algorithms to find shortest paths homotopic to given disjoint paths that wind amongst n point obstacles in the plane. Our deterministic algorithm runs in time O(k log n+nrootn), and the randomized version in time O(k log n + n(log n)(1+epsilon)), where k is the input plus output sizes of the paths.

引用

页码：411 / 423

页数：13

共 16 条

[1]

[Anonymous], 1989, The Design and Analysis of Spatial Data Structures

[2]

[Anonymous], 2000, Geometry, Spinors and Applications

[3] TRIANGULATING DISJOINT JORDAN CHAINS [J].

Bar-Yehuda, Reuven ;

Chazelle, Bernard .

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1994, 4 (04) :475-481

[4]

CABELLO S, 2002, 18 ANN S COMP GEOM, P160

[5] AN ALGORITHM FOR SEGMENT-DRAGGING AND ITS IMPLEMENTATION [J].

CHAZELLE, B .

ALGORITHMICA, 1988, 3 (02) :205-221

[6]

Chazelle B., 1982, 23rd Annual Symposium on Foundations of Computer Science, P339, DOI 10.1109/SFCS.1982.58

[7]

Cole R., 1984, 25th Annual Symposium on Foundations of Computer Science (Cat. No. 84CH2085-9), P65, DOI 10.1109/SFCS.1984.715902

[8]

DUNCAN CA, 2001, 9 S GRAPH DRAW GD 01, P162

[9]

EDELSBRUNNER H, 1981, B EATCS, V15, P34

[10]

EFRAT A, 2002, 18 ANN S COMP GEOM, P277

← 1 2 →