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
相关论文
共 50 条
  • [1] STORING SHORTEST PATHS FOR A POLYHEDRON
    CHEN, JD
    HAN, YJ
    LECTURE NOTES IN COMPUTER SCIENCE, 1991, 497 : 169 - 180
  • [2] THE NUMBER OF SHORTEST PATHS ON THE SURFACE OF A POLYHEDRON
    MOUNT, DM
    SIAM JOURNAL ON COMPUTING, 1990, 19 (04) : 593 - 611
  • [3] Approximating shortest paths on a nonconvex polyhedron
    Varadarajan, KR
    Agarwal, PK
    38TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1997, : 182 - 191
  • [4] Approximating shortest paths on a nonconvex polyhedron
    Varadarajan, KR
    Agarwal, PK
    SIAM JOURNAL ON COMPUTING, 2000, 30 (04) : 1321 - 1340
  • [5] Shortest paths between shortest paths
    Kaminski, Marcin
    Medvedev, Paul
    Milanic, Martin
    THEORETICAL COMPUTER SCIENCE, 2011, 412 (39) : 5205 - 5210
  • [6] Computing shortest paths with uncertainty
    Feder, Tomas
    Motwani, Rajeev
    O' Callaghan, Liadan
    Olston, Chris
    Panigrahy, Rina
    JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2007, 62 (01): : 1 - 18
  • [7] Computing Almost Shortest Paths
    Elkin, Michael
    ACM TRANSACTIONS ON ALGORITHMS, 2005, 1 (02) : 283 - 323
  • [8] Computing shortest paths with uncertainty
    Feder, T
    Motwani, R
    O'Callaghan, L
    Olston, C
    Panigrahy, R
    STACS 2003, PROCEEDINGS, 2003, 2607 : 367 - 378
  • [9] Computing shortest paths with comparisons and additions
    Pettie, S
    Ramachandran, V
    PROCEEDINGS OF THE THIRTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2002, : 267 - 276
  • [10] Computing homotopic shortest paths efficiently
    Efrat, A
    Kobourov, SG
    Lubiw, A
    ALGORITHMS-ESA 2002, PROCEEDINGS, 2002, 2461 : 411 - 423
12345