Computing an approximation of the 1-center problem on weighted terrain surfaces

ABSTRACT

In this article, we discuss the problem of determining a meeting point of a set of scattered robots R &equls; {r₁, r₂,…,r_s} in a weighted terrain P, which has n > s triangular faces. Our algorithmic approach is to produce a discretization of P by producing a graph G &equls; {V^G, E^G}, which lies on the surface of P. For a chosen vertex &pprime; ∈ V^G, we define ‖Π(r_i, &pprime;)‖ as the minimum weight cost of traveling from r_i to &pprime;. We show that min_{&pprime; ∈ V^G}{max_1≤i≤s {‖Π(r_i,&pprime;)‖}} ≤ min_p*∈P{max_1≤i≤s{‖Π(r_i,p*)‖}} + 2W|L|, where L is the longest edge of P, W is the maximum cost weight of a face of P, and p* is the optimal solution. Our algorithm requires O(snm log(snm) + snm²) time to run, where m = n in the Euclidean metric and m = n² in the weighted metric. However, we show, through experimentation, that only a constant value of m is required (e.g., m = 8) in order to produce very accurate solutions (< 1% error). Hence, for typical terrain data, the expected running time of our algorithm is O(sn log(sn)). Also, as part of our experiments, we show that by using geometrical subsets (i.e., 2D/3D convex hulls, 2D/3D bounding boxes, and random selection) of the robots we can improve the running time for finding &pprime;, with minimal or no additional accuracy error when comparing &pprime; to p*.

REFERENCES

• 1: Aleksandrov, L., Lanthier, M., Maheshwari, A., and Sack, J.-R. 1998. An epsilon-approximation algorithm for weighted shortest paths s on polyhedral surfaces. In Proceedings SWAT '98 (LNCS 1432). Stockholm, Sweden. 11--22.
• 2: Aleksandrov, L., Maheshwari, A., and Sack, J.-R. 2003. An improved approximation algorithm for computing geometric shortest paths. In Proceedings 14th Annual Symposium on the Fundamentals of Computation Theory. Malmo, Sweden. 246--257.
• 3: Aronov, B., van Kreveld, M., van Oostrum, R., and Varadarajan, K. 1998. Facility location on terrains. In Proceedings of the 9th International Symposium of Algorithms and Computation (LNCS 1533). Taejon, Korea. 19--28.
• 4: Dijkstra, R. 1959. A note on two problems in connection with graphs. Numerical Math. 1, 269--271.
• 5: Drezner, Z. 1984. The p-center problem: Heuristic and optimal algorithms. J. Operational Res. Soc. 35, 741--748.
• 6: Driscoll, J., Gabow, H., Shrairman, R., and Tarjan, R. 1988. Relaxed Heaps: An Alternative to Fibonacci Heaps with Applications to Parallel Computation. Commun. ACM 31, 11, 1343--1354.
• 7: Fredman, M. and Tarjan, R. 1987. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34, 3, 596--615.
• 8: Graham, R. L. 1972. An efficient algorithm for determining the convex hull of a finite planar set. Inform. Process. Lett. 1, 132--133.
• 9: Guibas, L. and Stolfi, J. 1985. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Trans. Graphics 4, 2, 75--123.
• 10: Kariv, O. and Hakimi, S. 1979. An algorithmic approach to network location problems I: The p-centers. Siam J. Appl. Math. 37, 3, 513--538.
• 11: Lanthier, M., Maheshwari, A., and Sack, J.-R. 1999. Shortest anisotropic paths on terrains. In Proceedings ICALP 99 (LNCS 1644). Prague, Czech Republic. 524--533.
• 12: Lanthier, M., Maheshwari, A., and Sack, J.-R. 2001. Approximating weighted shortest paths on polyhedral surfaces. Algorithmica 30, 4, 527--562.
• 13: Lanthier, M., Nussbaum, D., and Sack, J.-R. 2003. Parallel implementation of geometric shortest path algorithms. Parallel Comput. 29, 1445--1479.
• 14: Lee, D. and Preparata, F. 1984. Euclidean shortest paths in the presence of rectilinear barriers. Networks 14, 393--410.
• 15: Megiddo, N. 1983a. Applying parallel computation algorithms in the design of serial algorithms. J. ACM 30, 852--865.
• 16: Megiddo, N. 1983b. Linear-time algorithms for linear programming in R³ and related problems. SIAM J. Comput. 12, 759--776.
• 17: Mitchell, J. 1997. In Handbook of Discrete and Computational Geometry, J. Goodman and J. O'Rourke, Eds. CRC Press LLC, Boca Raton, FL. 445--466.
• 18: Mitchell, J. 2000. In Handbook on Computational Geometry, J.-R. Sack and J. Urrutia, Eds. Elsevier Science, Amsterdam. 633--701.
• 19: Mitchell, J. and Papadimitriou, C. 1991. The weighted region problem: Finding shortest paths through a weighted planar subdivision. J. ACM 38, 18--73.
• 20: Nussbaum, D. 1997. Rectilinear p-piercing problems. In ISSAC'97 International Symposium on Symbolic and Algebraic Computation. Maui, Hawaii.
• 21: Sharir, M. 1996. A near-linear algorithm for the planar 2-center problem. In Proceedings 12th ACM Symposium on Computational Geometry. Philadelphia, Pennsylvania. 110--121.
• 22: Sharir, M. and Schorr, A. 1986. On shortest paths in polyhedral spaces. SIAM J. Comput. 15, 193--215.
• 23: Sharir, M. and Welzl, E. 1996. Rectilinear and polygonal p-piercing and p-center problems. In Proceedings of the 12th ACM Symposium on Computational Geometry. Philadelphia, Pennsylvania. 122--132.
• 24: Sun, Z. and Reif, J. 2003. Adaptive and compact discretization for weighted region optimal path finding. In Proceedings of the 14th International Symposium on Fundamentals of Computation Theory (FCT2003) (LNCS 2751). Malmö, Sweden. 258--270.
• 25: van Oostrum, R. 1999. Geometric algorithms for geographic information systems. Ph.D. thesis, Department of Computer Science, Utrecht University.
• 26: van Trigt, M. 1995. Proximity problems on polyhedral terrains. M.S. thesis, Department of Computer Science, Utrecht University.
• 27: Welzl, E. 1991. Lecture Notes in Computer Science: New Results and New Trends in Computer Science, H. Maurer, Eds. Vol. 555. Springer-Verlag, New York. 359--370.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation

Keywords:
1-Center, algorithms, approximation, meeting point, robots, shortest path, terrain, weighted