Finding optimal weighted bridges with applications

ABSTRACT

The computation of shortest paths, distances and feature relationships is a key problem in many applications. In finding shortest distances or paths one often must respect features of the domain. For example, in medical applications such as radiation therapy, the features may include tissue density, risk to radiation exposure, etc. In computing an optimal treatment plan, one can think of these features as weights that effect a cost per unit travel distance function. In this model, the cost of travelling through 2 cm of dense bone might be more than the cost of travelling through 5 cm of very soft tissue. One possible way to model such problems is as shortest path problems in weighted regions.A special case of shortest path problems in weighted regions is that of computing an optimal weighted bridge between two regions. In this version, we are given two disjoint convex polygons P and Q in a weighted subdivision R. A weighted bridge, Bw, is a path from a point p ∈ P to a point q ∈ Q that connects P and Q such that the sum of the weighted length of Bw and the maximum weighted distance from any point in P to p and from any point in Q to q is minimized. The goal is to compute an optimal weighted bridge between P and Q.In this paper, we describe 2-factor and (1 + ∈)-factor approximation schemes for finding optimal 1-link weighted bridges between a pair of convex polygons. We also describe how these techniques can be extended to k-link weighted bridges and weighted bridges where the number of links is not restricted.

REFERENCES

• 1: A. Aggarwal , L. J. Guibas , J. Saxe , P. W. Shor, A linear-time algorithm for computing the Voronoi diagram of a convex polygon, Discrete & Computational Geometry, v.4 n.6, p.591-604, Sep. 1989 [doi>10.1007/BF02187749]
• 2: Lyudmil Aleksandrov , Mark Lanthier , Anil Maheshwari , Jörg-Rüdiger Sack, An epsilon-Approximation for Weighted Shortest Paths on Polyhedral Surfaces, Proceedings of the 6th Scandinavian Workshop on Algorithm Theory, p.11-22, July 08-10, 1998
• 3: Lyudmil Aleksandrov , Anil Maheshwari , Jörg-Rüdiger Sack, Approximation algorithms for geometric shortest path problems, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.286-295, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335339]
• 4: L. Aleksandrov , A. Maheshwari , J.-R. Sack, Determining approximate shortest paths on weighted polyhedral surfaces, Journal of the ACM (JACM), v.52 n.1, p.25-53, January 2005 [doi>10.1145/1044731.1044733]
• 5: Binary Bhattacharya , Robert Benkoczi, On computing the optimal bridge between two convex polygons, Information Processing Letters, v.79 n.5, p.215-221, September 15, 2001 [doi>10.1016/S0020-0190(00)00228-3]
• 6: Leizhen Cai , Yinfeng Xu , Binhai Zhu, Computing the optimal bridge between two convex polygons, Information Processing Letters, v.69 n.3, p.127-130, Feb. 12, 1999 [doi>10.1016/S0020-0190(99)00003-4]
• 7: D. 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.
• 8: D. Z. Chen, X. Hu, and J. Xu. Optimal beam penetration in two and three dimensions. Journal of Combinatorial Optimization, 7(2):111--136, 2003.
• 9: Ovidiu Daescu, Improved Optimal Weighted Links Algorithms, Proceedings of the International Conference on Computational Science-Part III, p.65-74, April 21-24, 2002
• 10: O. Daescu, J. S. B. Mitchell, S. Ntafos, J. D. Palmer, and C. K. Yap. k-link shortest paths in weighted subdivisions. In 9th Annual Workshop on Algorithms and Data Structures, Aug 2005.
• 11: O. Daescu and J. Palmer. Minimum separation in weighted subdivisions. Submitted to the International Journal of Computational Geometry and Applications, August 2003.
• 12: L. Gewali, A. Meng, J. S. B. Mitchell, and S. Ntafos. Path planning in 0/1/∞ weighted regions with applications. ORSA Journal on Computing, 2(3):253--272, 1990.
• 13: S. Kim and C. Shin. Computing the optimal bridge between two polygons. Theory of Computing Systems, 34:337--354, 2001.
• 14: Mark Lanthier , Anil Maheshwari , Jörg-Rüdiger Sack, Approximating weighted shortest paths on polyhedral surfaces, Proceedings of the thirteenth annual symposium on Computational geometry, p.485-486, June 04-06, 1997, Nice, France [doi>10.1145/262839.263101]
• 15: M. Lanthier, A. Maheshwari, and J.-R. Sack. Approximating shortest paths on weighted polyhedral surfaces. Algorithmica, 30(4):527--562, 2001.
• 16: Christian S. Mata , Joseph S. B. Mitchell, A new algorithm for computing shortest paths in weighted planar subdivisions (extended abstract), Proceedings of the thirteenth annual symposium on Computational geometry, p.264-273, June 04-06, 1997, Nice, France [doi>10.1145/262839.262983]
• 17: J. S. B. Mitchell. Geometric shortest paths and network optimization. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry. Elsevier Science, 2000.
• 18: 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]
• 19: L. Palios. A linear-time algorithm for computing the optimal bridge connecting two disjoint convex polygons. In Proc. 17th European Workshop on Computational Geometry, 2001.
• 20: J. Reif and Z. Sun. An efficient approximation algorithm for weighted region shortest path problem. In Proceedings of the 4th Workshop on Algorithmic Foundations of Robotics, Hanover, New Hampshire, Mar. 16--18 2000. A. K. Peters Ltd.
• 21: Z. Sun and J. H. Reif. Adaptive and compact discretization for weighted region optimal path finding. In 14th Symposium on Fundamentals of Computation Theory, Malm Hgskola, Sweden, August 12--15, 2003, Lecture Notes in Computer Science. Springer-Verlag, 2003.
• 22: Xuehou Tan, On optimal bridges between two convex regions, Information Processing Letters, v.76 n.4-6, p.163-168, Dec.31 2000 [doi>10.1016/S0020-0190(00)00143-5]
• 23: Takeshi Tokuyama, Efficient algorithms for the minimum diameter bridge problem, Computational Geometry: Theory and Applications, v.24 n.1, p.11-18, January 2003

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

General Terms:
Algorithms

Keywords:
optimal bridges, path planning, weighted regions