Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

This paper studies real-world road networks from an algorithmic perspective, focusing on empirical studies that yield useful properties of road networks that can be exploited in the design of fast algorithms that deal with geographic data. Unlike previous approaches, our study is not based on the assumption that road networks are planar graphs. Indeed, based on the a number of experiments we have performed on the road networks of the 50 United States and District of Columbia, we provide strong empirical evidence that road networks are quite non-planar. Our approach therefore instead is directed at finding algorithmically-motivated properties of road networks as non-planar geometric graphs, focusing on alternative properties of road networks that can still lead to efficient algorithms for such problems as shortest paths and Voronoi diagrams. In particular, we study road networks as multiscale-dispersed graphs, which is a concept we formalize in terms of disk neighborhood systems. This approach allows us to develop fast algorithms for road networks without making any additional assumptions about the distribution of edge weights. In fact, our algorithms can allow for non-metric weights.

REFERENCES

• 1: L. Aceto and A. Ingolfsdottir. Computer Scientist: 21st Century Renaissance Man, 2007. http://www.ru.is/faculty/luca/PAPERS/renaissance-man.pdf.
• 2: N. M. Amato, M. T. Goodrich, and E. A. Ramos. A randomized algorithm for triangulating a simple polygon in linear time. Discrete Comput. Geom., 26(2):245--265, 2001.
• 3: Deganit Armon , John H. Reif, A Dynamic Separator Algorithm, Proceedings of the Third Workshop on Algorithms and Data Structures, p.107-118, August 11-13, 1993
• 4: Sanjeev Arora , Bernard Chazelle, Is the thrill gone?, Communications of the ACM, v.48 n.8, August 2005 [doi>10.1145/1076211.1076233]
• 5: Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991 [doi>10.1145/116873.116880]
• 6: F. Aurenhammer and R. Klein. Voronoi diagrams. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 201--290. Elsevier Science Publishers B. V. North-Holland, Amsterdam, 2000.
• 7: Michael Batty , Paul Longley, Fractal cities: a geometry of form and function, Academic Press Professional, Inc., San Diego, CA, 1994
• 8: Prosenjit Bose , Luc Devroye, On the stabbing number of a random Delaunay triangulation, Computational Geometry: Theory and Applications, v.36 n.2, p.89-105, February, 2007 [doi>10.1016/j.comgeo.2006.05.005]
• 9: Bernard Chazelle, Triangulating a simple polygon in linear time, Discrete & Computational Geometry, v.6 n.5, p.485-524, 1991 [doi>10.1007/BF02574703]
• 10: B. Chazelle. Could Your iPod Be Holding the Greatest Mystery in Modern Science? MAA Math Horizons (Codes, Cryptography, and National Security), 13, 2006. http://www.cs.princeton.edu/~chazelle/pubs/ipod.pdf.
• 11: B. Chazelle. The Algorithm: Idiom of Modern Science, 2006. http://www.cs.princeton.edu/~chazelle/pubs/algorithm.html.
• 12: Y. H. Chou. Exploring Spatial Analysis in GIS. Onword Press, 1996.
• 13: A. Condon. RNA Molecules: Glimpses Through an Algorithmic Lens. In LATIN 2006: Theoretical Informatics, volume 3887 of Springer LNCS, pages 8--10. Springer, 2006.
• 14: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 15: David Eppstein, Setting Parameters by Example, SIAM Journal on Computing, v.32 n.3, p.643-653, 2003 [doi>10.1137/S0097539700370084]
• 16: David Eppstein , Gary L. Miller , Shang-Hua Teng, A deterministic linear time algorithm for geometric separators and its applications, Proceedings of the ninth annual symposium on Computational geometry, p.99-108, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161005]
• 17: M. Erwig. The Graph Voronoi Diagram with Applications. Networks, 36(3):156--163, 2000.
• 18: Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
• 19: Andrew V. Goldberg, Scaling algorithms for the shortest paths problem, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.222-231, January 25-27, 1993, Austin, Texas, United States
• 20: Andrew V. Goldberg , Chris Harrelson, Computing the shortest path: A search meets graph theory, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 21: Michael T. Goodrich, Planar separators and parallel polygon triangulation, Journal of Computer and System Sciences, v.51 n.3, p.374-389, Dec. 1995 [doi>10.1006/jcss.1995.1076]
• 22: M. T. Goodrich and R. Tamassia. Algorithm Design: Foundations, Analysis, and Internet Examples. John Wiley & Sons, New York, NY, 2002.
• 23: Monika R. Henzinger , Philip Klein , Satish Rao , Sairam Subramanian, Faster shortest-path algorithms for planar graphs, Journal of Computer and System Sciences, v.55 n.1, p.3-23, Aug. 1997 [doi>10.1006/jcss.1997.1493]
• 24: Martin Holzer , Frank Schulz , Dorothea Wagner , Thomas Willhalm, Combining speed-up techniques for shortest-path computations, Journal of Experimental Algorithmics (JEA), 10, 2005 [doi>10.1145/1064546.1180616]
• 25: G. A. Klunder , H. N. Post, The shortest path problem on large-scale real-road networks, Networks, v.48 n.4, p.182-194, December 2006 [doi>10.1002/net.v48:4]
• 26: P. Koebe. Kontaktprobleme der konformen Abbildung. Ber. Verh. Sächs. Akademie der Wissenschaften Leipzig, Math.-Phys. Klasse, 88:141--164, 1936.
• 27: R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM J. Appl. Math., 36:177--189, 1979.
• 28: Kurt Mehlhorn, A faster approximation algorithm for the Steiner problem in graphs, Information Processing Letters, v.27 n.3, p.125-128, March 25, 1988 [doi>10.1016/0020-0190(88)90066-X]
• 29: Ulrich Meyer, Single-source shortest-paths on arbitrary directed graphs in linear average-case time, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.797-806, January 07-09, 2001, Washington, D.C., United States
• 30: Gary L Miller, Finding small simple cycle separators for 2-connected planar graphs, Journal of Computer and System Sciences, v.32 n.3, p.265-279, June 1986 [doi>10.1016/0022-0000(86)90030-9]
• 31: Gary L. Miller , Shang-Hua Teng , William Thurston , Stephen A. Vavasis, Geometric Separators for Finite-Element Meshes, SIAM Journal on Scientific Computing, v.19 n.2, p.364-386, March 1998 [doi>10.1137/S1064827594262613]
• 32: Gary L. Miller , Shang-Hua Teng , William Thurston , Stephen A. Vavasis, Separators for sphere-packings and nearest neighbor graphs, Journal of the ACM (JACM), v.44 n.1, p.1-29, Jan. 1997 [doi>10.1145/256292.256294]
• 33: Bojan Mohar, A polynomial time circle packing algorithm, Discrete Mathematics, v.117 n.1-3, p.257-263, July 1, 1993 [doi>10.1016/0012-365X(93)90340-Y]
• 34: C. Papadimitriou. The Algorithmic Lens: How the Computational Perspective is Transforming the Sciences, 2007. FCRC CCC presentation, http://lazowska.cs.washington.edu/fcrc/Christos.FCRC.pdf.
• 35: Rajeev Raman, Recent results on the single-source shortest paths problem, ACM SIGACT News, v.28 n.2, p.81-87, June 1997 [doi>10.1145/261342.261352]
• 36: P. Sanders and D. Schultes. Highway Hierarchies Hasten Exact Shortest Path Queries. In Proceedings 17th European Symposium on Algorithms (ESA), volume 3669 of Springer LNCS, pages 568--579. Springer, 2005.
• 37: Robert Sedgewick , Jeffrey Scott Vitter, Shortest paths in Euclidean graphs, Algorithmica, v.1 n.1, p.31-48, Jan. 1986 [doi>10.1007/BF01840435]
• 38: Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]
• 39: Daniel A. Spielman , Shang-Hua Teng, Disk packings and planar separators, Proceedings of the twelfth annual symposium on Computational geometry, p.349-358, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237404]
• 40: Mikkel Thorup, Undirected single-source shortest paths with positive integer weights in linear time, Journal of the ACM (JACM), v.46 n.3, p.362-394, May 1999 [doi>10.1145/316542.316548]
• 41: Jeannette M. Wing, Computational thinking, Communications of the ACM, v.49 n.3, March 2006 [doi>10.1145/1118178.1118215]
• 42: F. Benjamin Zhan , Charles E. Noon, Shortest Path Algorithms: An Evaluation Using Real Road Networks, Transportation Science, v.32 n.1, p.65-73, January 1998 [doi>10.1287/trsc.32.1.65]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms

Keywords:
Voronoi diagrams, algorithmic lens, circle arrangements, disk neighborhood systems, multiscale-dispersed graphs, road networks, shortest paths