Shortest paths on a polyhedron .1. Computing shortest paths

被引：74

作者：

Chen, JD ^{[1
]}

Han, YJ ^{[1
]}

机构：

[1] UNIV KENTUCKY,DEPT COMP SCI,LEXINGTON,KY 40506

来源：

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS | 1996年 / 6卷 / 02期

关键词：

shortest path; motion planning; nonconvex polyhedron; single source shortest path; computational geometry; computational robotics;

D O I：

10.1142/S0218195996000095

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present an algorithm for determining the shortest path between any two points along the surface of a polyhedron which need not be convex. This algorithm also computes for any source point on the surface of a polyhedron the inward layout and the subdivision of the polyhedron which can be used for processing queries of shortest paths between the source point and any destination point. Our algorithm uses a new approach which deviates from the conventional ''continuous Dijkstra'' technique. Our algorithm has time complexity O(n(2)) and space complexity Theta(n).

引用

页码：127 / 144

页数：18

共 21 条

[1]

AGARWAL P, 1990, LNCS, V447

[2]

[Anonymous], 1975, P 16 ANN IEEE S FDN

[3]

ARONOV B, P 1991 ACM S COMP GE

[4]

CANNY J, P 1987 IEEE FOCS, P39

[5] TRIANGULATING A SIMPLE POLYGON IN LINEAR TIME [J].

CHAZELLE, B .

DISCRETE & COMPUTATIONAL GEOMETRY, 1991, 6 (05) :485-524

[6]

CHEN J, LECTURE NOTES COMPUT, V497, P169

[7]

Dijkstra E. W., 1959, NUMER MATH, V1, P269, DOI DOI 10.1007/BF01386390

[8] OPTIMAL SEARCH IN PLANAR SUBDIVISIONS [J].

KIRKPATRICK, D .

SIAM JOURNAL ON COMPUTING, 1983, 12 (01) :28-35

[9] EUCLIDEAN SHORTEST PATHS IN THE PRESENCE OF RECTILINEAR BARRIERS [J].

LEE, DT ;

PREPARATA, FP .

NETWORKS, 1984, 14 (03) :393-410

[10]

LEE DT, 1978, ACT12 U ILL COORD SC

← 1 2 3 →