Skip to main content
Article
Energetic Path Finding Across Massive Terrain Data
Lecture Notes in Computer Science
  • Andrew Tsui, California Polytechnic State University - San Luis Obispo
  • Zoë J. Wood, California Polytechnic State University - San Luis Obispo
Publication Date
1-1-2009
Abstract

Throughout history, the primary means of transportation for humans has been on foot. We present a software tool which can help visualize and predict where historical trails might lie through the use of a human-centered cost metric, with an emphasis on the ability to generate paths which traverse several thousand kilometers. To accomplish this, various graph simplification and path approximation algorithms are explored. We show that it is possible to restrict the search space for a path finding algorithm while not sacrificing accuracy. Combined with a multi-threaded variant of Dijkstra’s shortest path algorithm, we present a tool capable of computing a path of least caloric cost across the contiguous US, a dataset containing over 19 billion datapoints, in under three hours on a 2.5 Ghz dual core processor. The potential archaeological and historical applications are demonstrated on several examples.

Disciplines
Citation Information
Andrew Tsui and Zoë J. Wood. "Energetic Path Finding Across Massive Terrain Data" Lecture Notes in Computer Science Vol. 5876 (2009) p. 879 - 888
Available at: http://works.bepress.com/zwood/12/