This paper introduces a new algorithm for quickly answering repetitive leas
t-cost queries between pairs of points on the earth's surface as represente
d by digital topographical maps. The algorithm uses a three-step process; p
reprocessing, geometrically modified Dijkstra search, and postprocessing, T
he preprocessing step computes and saves highly valuable global information
that describes the underlying geometry of the terrain. The search step sol
ves shortest path queries using a modified Dijkstra algorithm that takes ad
vantage of the preprocessed information to "jump" quickly across flat terra
in and decide whether a path should go over or through a high-cost region.
The final step is a path improvement process that straightens and globally
improves the path. Our algorithm partitions the search space into free regi
ons and obstacle regions. However, unlike other algorithms using this appro
ach, our algorithm keeps the option of passing through an obstacle region.