1-link shortest paths in weighted regions

ABSTRACT

We illustrate the Link Solver software for computing 1-link shortest paths in weighted regions. The Link Solver implements a prune-and-search method that can be used to approximate an optimal solution within a user specified precision. The theoretical foundation of the method is a result stating that an optimal solution goes through a vertex of the subdivision. This result provides a way to discretize the problem with respect to vertices of interest which in turn leads to efficient algorithms.

REFERENCES

• 1: D.Z. Chen, O. Daescu, X. Hu, X. Wu and J. Xu. Determining an optimal penetration among weighted regions in two and three dimensions. Journal of Combinatorial Optimization 5(1):59--79, 2001.
• 2: Ovidiu Daescu, Improved Optimal Weighted Links Algorithms, Proceedings of the International Conference on Computational Science-Part III, p.65-74, April 21-24, 2002
• 3: Ovidiu Daescu , Ashish Bhatia, Computing Optimal Trajectories for Medical Treatment Planning and Optimization, Proceedings of the International Conference on Computational Science-Part III, p.227-233, April 21-24, 2002
• 4: Joseph S. B. Mitchell , Christos H. Papadimitriou, The weighted region problem: finding shortest paths through a weighted planar subdivision, Journal of the ACM (JACM), v.38 n.1, p.18-73, Jan. 1991 [doi>10.1145/102782.102784]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

General Terms:
Algorithms, Experimentation