Approximate distance oracles for geometric spanners

ABSTRACT

Given an arbitrary real constant ϵ > 0, and a geometric graph G in d-dimensional Euclidean space with n points, O(n) edges, and constant dilation, our main result is a data structure that answers (1 + ϵ)-approximate shortest-path-length queries in constant time. The data structure can be constructed in O(n log n) time using O(n log n) space. This represents the first data structure that answers (1 + ϵ)-approximate shortest-path queries in constant time, and hence functions as an approximate distance oracle. The data structure is also applied to several other problems. In particular, we also show that approximate shortest-path queries between vertices in a planar polygonal domain with “rounded” obstacles can be answered in constant time. Other applications include query versions of closest-pair problems, and the efficient computation of the approximate dilations of geometric graphs. Finally, we show how to extend the main result to answer (1 + ϵ)-approximate shortest-path-length queries in constant time for geometric spanner graphs with m = ω(n) edges. The resulting data structure can be constructed in O(m + n log n) time using O(n log n) space.

REFERENCES

• 1: Pankaj K. Agarwal , Sariel Har-Peled , Meetesh Karia, Computing approximate shortest paths on convex polytopes, Proceedings of the sixteenth annual symposium on Computational geometry, p.270-279, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336213]
• 2: Pankaj K. Agarwal , Sariel Har-Peled , Micha Sharir , Kasturi R. Varadarajan, Approximating shortest paths on a convex polytope in three dimensions, Journal of the ACM (JACM), v.44 n.4, p.567-584, July 1997 [doi>10.1145/263867.263869]
• 3: D. Aingworth , C. Chekuri , P. Indyk , R. Motwani, Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication), SIAM Journal on Computing, v.28 n.4, p.1167-1181, Aug. 1999 [doi>10.1137/S0097539796303421]
• 4: Srinivasa Rao Arikati , Danny Z. Chen , L. Paul Chew , Gautam Das , Michiel H. M. Smid , Christos D. Zaroliagis, Planar Spanners and Approximate Shortest Path Queries among Obstacles in the Plane, Proceedings of the Fourth Annual European Symposium on Algorithms, p.514-528, September 25-27, 1996
• 5: Sanjeev Arora, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, Journal of the ACM (JACM), v.45 n.5, p.753-782, Sept. 1998 [doi>10.1145/290179.290180]
• 6: S. Arora, Nearly linear time approximation schemes for Euclidean TSP and other geometric problems, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.554, October 19-22, 1997
• 7: Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
• 8: Surender Baswana , Sandeep Sen, Approximate distance oracles for unweighted graphs in Õ (n²) time, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 9: Michael A. Bender , Martin Farach-Colton, The LCA Problem Revisited, Proceedings of the 4th Latin American Symposium on Theoretical Informatics, p.88-94, April 10-14, 2000
• 10: Paul B. Callahan, Dealing with higher dimensions: the well-separated pair decomposition and its applications, Johns Hopkins University, Baltimore, MD, 1995
• 11: Paul B. Callahan , S. Rao Kosaraju, Faster algorithms for some geometric graph problems in higher dimensions, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.291-300, January 25-27, 1993, Austin, Texas, United States
• 12: Paul B. Callahan , S. Rao Kosaraju, A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields, Journal of the ACM (JACM), v.42 n.1, p.67-90, Jan. 1995 [doi>10.1145/200836.200853]
• 13: Chan, T. M. 1998. Approximate nearest neighbor queries revisited. Discr. Comput. Geom. 20, 359--373.
• 14: Danny Z. Chen, On the all-pairs Euclidean short path problem, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.292-301, January 22-24, 1995, San Francisco, California, United States
• 15: Chen, D. Z., Daescu, O., and Klenk, K. S. 2001. On geometric path query problems. Int. J. Comput. Geom. Appl. 11, 617--645.
• 16: Danny Z. Chen , Kevin S. Klenk , Hung-Yi T. Tu, Shortest Path Queries Among Weighted Obstacles in the Rectilinear Plane, SIAM Journal on Computing, v.29 n.4, p.1223-1246, Feb. 2000 to March 2000 [doi>10.1137/S0097539796307194]
• 17: K. Clarkson, Approximation algorithms for shortest path motion planning, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.56-65, January 1987, New York, New York, United States [doi>10.1145/28395.28402]
• 18: Edith Cohen, Fast Algorithms for Constructing t-Spanners and Paths with Stretch t, SIAM Journal on Computing, v.28 n.1, p.210-236, Feb. 1999 [doi>10.1137/S0097539794261295]
• 19: Das, G., and Narasimhan, G. 1997. A fast algorithm for constructing sparse Euclidean spanners. Int. J. Comput. Geom. Appl. 7, 297--315.
• 20: Gautam Das , Deborah Joseph, Which Triangulations Approximate the Complete Graph?, Proceedings of the International Symposium on Optimal Algorithms, p.168-192, May 29-June 02, 1989
• 21: de Berg, M., Katz, M. J., van der Stappen, A. F., and Vleugels, J. 2002. Realistic input models for geometric algorithms. Algorithmica 34, 81--97.
• 22: Dorit Dor , Shay Halperin , Uri Zwick, All-Pairs Almost Shortest Paths, SIAM Journal on Computing, v.29 n.5, p.1740-1759, March 2000 [doi>10.1137/S0097539797327908]
• 23: Gao, J., Guibas, L. J., Hershberger, J., Zhang, L., and Zhu, A. 2003. Discrete mobile centers. Discr. Comput. Geom. 30, 45--63.
• 24: Gonzalez, T. 1975. Algorithms on sets and related problems. Tech. Rep., Department of Computer Science, University of Oklahoma, Norman.
• 25: Joachim Gudmundsson , Christos Levcopoulos , Giri Narasimhan, Fast Greedy Algorithms for Constructing Sparse Geometric Spanners, SIAM Journal on Computing, v.31 n.5, p.1479-1500, 2002 [doi>10.1137/S0097539700382947]
• 26: Gudmundsson, J., Narasimhan, G., and Smid, M. 2005. Fast pruning of geometric spanners. In Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 3404. Springer, Berlin, 508--520.
• 27: Joachim Gudmundsson , Christos Levcopoulos , Giri Narasimhan , Michiel Smid, Approximate distance oracles for geometric graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.828-837, January 06-08, 2002, San Francisco, California
• 28: Joachim Gudmundsson , Christos Levcopoulos , Giri Narasimhan , Michiel H. M. Smid, Approximate Distance Oracles Revisited, Proceedings of the 13th International Symposium on Algorithms and Computation, p.357-368, November 21-23, 2002
• 29: L. J. Guibas , J. Hershberger, Optimal shortest path queries in a simple polygon, Journal of Computer and System Sciences, v.39 n.2, p.126-152, Oct. 1989 [doi>10.1016/0022-0000(89)90041-X]
• 30: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 31: Sariel Har-Peled, Approximate shortest paths and geodesic diameters on convex polytopes in three dimensions, Proceedings of the thirteenth annual symposium on Computational geometry, p.359-365, June 04-06, 1997, Nice, France [doi>10.1145/262839.263003]
• 32: Dov Harel , Robert Endre Tarjan, Fast algorithms for finding nearest common ancestors, SIAM Journal on Computing, v.13 n.2, p.338-355, May 1984 [doi>10.1137/0213024]
• 33: John Hershberger , Subhash Suri, An Optimal Algorithm for Euclidean Shortest Paths in the Plane, SIAM Journal on Computing, v.28 n.6, p.2215-2256, Dec. 1999 [doi>10.1137/S0097539795289604]
• 34: P. Indyk, Algorithmic Applications of Low-Distortion Geometric Embeddings, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.10, October 14-17, 2001
• 35: Kapoor, S., Maheshwari, S. N., and Mitchell, J. S. B. 1997. An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane. Discr. Comput. Geom. 18, 377--383.
• 36: J. Mark Keil , Carl A. Gutwin, Classes of graphs which approximate the complete Euclidean graph, Discrete & Computational Geometry, v.7 n.1, p.13-28, 1992 [doi>10.1007/BF02187821]
• 37: Lee, D. T., and Wu, Y. F. 1986. Geometric complexity of some location problems. Algorithmica 1, 193--211.
• 38: Mitchell, J. S. B. 1996. Shortest paths among obstacles in the plane. Int. J. Comput. Geom. Appl. 6, 309--332.
• 39: Mitchell, J. S. B. 1998. Geometric shortest paths and network optimization. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, eds. Elsevier Science, Amsterdam, Chapter 24, 633--701.
• 40: Joseph S. B. Mitchell, Shortest paths and networks, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 41: Giri Narasimhan , Michiel Smid, Approximating the Stretch Factor of Euclidean Graphs, SIAM Journal on Computing, v.30 n.3, p.978-989, 2000 [doi>10.1137/S0097539799361671]
• 42: Mark H. Overmars , A. Frank van der Stappen, Range searching and point location among fat objects, Journal of Algorithms, v.21 n.3, p.629-656, Nov. 1996 [doi>10.1006/jagm.1996.0063]
• 43: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 44: Pyrga, E., Schulz, F., Wagner, D., and Zaroliagis, C. 2004. Experimental comparison of shortest path approaches for timetable information. In Proceedings of the 6th Workshop on Algorithm Engineering and Experiments. Lecture Notes in Computer Science. Springer, Berlin, 88--99.
• 45: Salowe, J. S. 1991. Constructing multidimensional spanner graphs. Int. J. Comput. Geom. Appl. 1, 99--107.
• 46: Baruch Schieber , Uzi Vishkin, On finding lowest common ancestors: simplification and parallelization, SIAM Journal on Computing, v.17 n.6, p.1253-1262, Dec. 1988 [doi>10.1137/0217079]
• 47: Subhash Suri, Polygons, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 48: Mikkel Thorup, Compact oracles for reachability and approximate distances in planar digraphs, Journal of the ACM (JACM), v.51 n.6, p.993-1024, November 2004 [doi>10.1145/1039488.1039493]
• 49: Mikkel Thorup , Uri Zwick, Approximate distance oracles, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.183-192, July 2001, Hersonissos, Greece [doi>10.1145/380752.380798]
• 50: Wagner, D., and Willhalm, T. 2003. Geometric speed-up techniques for finding shortest paths in large sparse graphs. In Proceedings of the 11th Annual European Symposium on Algorithms (ESA), Lecture Notes in Computer Science, vol. 2832. Springer, Berlin, 776--787.
• 51: Wagner, D., Willhalm, T., and Zaroliagis, C. 2004. Dynamic shortest path containers. In Proceedings of the 3rd Workshop on Algorithmic Methods and Models for Optimization of Railways. Electronic Notes in Theoretical Computer Science, vol. 92. Elsevier, 65--84.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory

Keywords:
Shortest paths, approximation algorithm, computational geometry, geometric graphs, spanners