BUSHWHACK: An approximation algorithm for minimal paths through pseudo-euclidean spaces


Journal Article

In this paper we define piecewise pseudo-Euclidean optimal path problems, where each region has a distinct cost metric of a class we call pseudo-Euclidean, that allows the path cost to possibly vary within the region in a predictable and efficiently computable way. This pseudo-Euclidean class of costs allows us to model a wide variety of various geographical features. We provide an approximation algorithm named BUSHWHACK that efficiently solves these piecewise pseudo-Euclidean optimal path problems. BUSHWHACK uses a previously known technique of dynamically generating a discretization in progress. However, it combines with this technique a "lazy" and best-first path propagation scheme so that fewer edges need to be added into the discretization. We show both analytically and experimentally that BUSHWHACK is more efficient than approximation algorithms based on Dijkstra's algorithm. © 2001 Springer Berlin Heidelberg.

Full Text

Duke Authors

Cited Authors

  • Sun, Z; Reif, J

Published Date

  • December 1, 2001

Published In

Volume / Issue

  • 2223 LNCS /

Start / End Page

  • 160 - 171

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

Digital Object Identifier (DOI)

  • 10.1007/3-540-45678-3_15

Citation Source

  • Scopus