• DocumentCode
    2093933
  • Title

    Path planning above a polyhedral terrain

  • Author

    Zarrabi-Zadeh, Hamid

  • Author_Institution
    Sch. of Comput. Sci., Waterloo Univ., Ont.
  • fYear
    2006
  • fDate
    15-19 May 2006
  • Firstpage
    873
  • Lastpage
    876
  • Abstract
    We consider the problem of path planning above a polyhedral terrain and present a new algorithm that for any p ges 1, computes a (c + epsi)-approximation to the Lp-shortest path above a polyhedral terrain in O(n/epsi log n log log n) time and O(n log n) space, where n is the number of vertices of the terrain, and c = 2(p-1)p/. This leads to an epsi-approximation algorithm for the problem in L1 metric, and a (radic2 + epsi)-factor approximation algorithm in Euclidean space
  • Keywords
    approximation theory; computational complexity; path planning; robots; Euclidean space; approximation algorithm; path planning; polyhedral terrain; Approximation algorithms; Computer science; Euclidean distance; Extraterrestrial measurements; Motion planning; Path planning; Robot motion; Shortest path problem;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Robotics and Automation, 2006. ICRA 2006. Proceedings 2006 IEEE International Conference on
  • Conference_Location
    Orlando, FL
  • ISSN
    1050-4729
  • Print_ISBN
    0-7803-9505-0
  • Type

    conf

  • DOI
    10.1109/ROBOT.2006.1641819
  • Filename
    1641819
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2093933