Approximate Euclidean shortest paths in 3-space

被引：18

作者：

Choi, JS ^{[1
]}

Sellen, J ^{[1
]}

Yap, CK ^{[1
]}

机构：

[1] NYU,COURANT INST MATH SCI,NEW YORK,NY 10012

来源：

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS | 1997年 / 7卷 / 04期

关键词：

approximate Euclidean shortest path; exact geometric computation;

D O I：

10.1142/S0218195997000181

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Papadimitriou's approximation approach to the Euclidean shortest path (ESP) in 3-space is revisited. As this problem is NP-hard, his approach represents an important step towards practical algorithms. However, there are several gaps in the original description. Besides giving a complete treatment in the framework of bit complexity, we also improve on his subdivision method. Among the tools needed are root-separation bounds and nontrivial applications of Brent's complexity bounds on evaluation of elementary functions using floating point numbers.

引用

页码：271 / 295

页数：25

共 13 条

[1]

Aho A., 1976, DESIGN ANAL COMPUTER

[2]

[Anonymous], VECTOR TENSOR ANAL

[3] FAST MULTIPLE-PRECISION EVALUATION OF ELEMENTARY FUNCTIONS [J].