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

ABSTRACT

A geometric graph is a graph embedded in the plane with vertices at points and edges drawn as curves (which are usually straight line segments) between those points. The average transversal complexity of a geometric graph is the number of edges of that graph that are crossed by random line or line segment.

In this paper, we study the average transversal complexity of road networks. By viewing road networks as multiscale-dispersed graphs, we show that a random line will cross the edges of such a graph O(√n) times on average. In addition, we provide by empirical evidence from experiments on the road networks of the fifty states of United States and the District of Columbia that this bound holds in practice and has a small constant factor. Combining this result with data structuring techniques from computational geometry, allows us to show that we can then do point location and ray-shooting navigational queries with respect to road networks in O(√n log n) expected time. Finally, we provide empirical justification for this claim as well.

REFERENCES

• 1: N. Alon and P. Erdős. Disjoint edges in geometric graphs. Discrete Comput. Geom., 4:287--290, 1989.
• 2: Bernard Chazelle , Herbert Edelsbrunner , Michelangelo Grigni , Leonidas Guibas , John Hershberger , Micha Sharir , Jack Snoeyink, Ray shooting in polygons using Geodesic triangulations, Proceedings of the 18th international colloquium on Automata, languages and programming, p.661-673, June 1991, Madrid, Spain
• 3: Y. H. Chou. Exploring Spatial Analysis in GIS. Onword Press, 1996.
• 4: Richard Cole, Searching and sorting similar lists, Journal of Algorithms, v.7 n.2, p.202-220, June 1986 [doi>10.1016/0196-6774(86)90004-0]
• 5: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 6: R. A. Dwyer. Voronoi diagrams of random lines and flats. Discrete&Computational Geometry, 17(2):123--136, 1997.
• 7: Ta. Asano, A new point-location algorithm and its practical efficiency: comparison with existing algorithms, ACM Transactions on Graphics (TOG), v.3 n.2, p.86-109, April 1984 [doi>10.1145/357337.357338]
• 8: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 9: David Eppstein , Michael T. Goodrich, Studying (non-planar) road networks through an algorithmic lens, Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems, November 05-07, 2008, Irvine, California [doi>10.1145/1463434.1463455]
• 10: David Eppstein , Michael T. Goodrich , Darren Strash, Linear-time algorithms for geometric graphs with sublinearly many crossings, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.150-159, January 04-06, 2009, New York, New York
• 11: I. Fáry. On straight lines representation of planar graphs. Acta Univ. Szeged. Sect. Sci. Math., 11:229--233, 1948.
• 12: S. Felsner. Geometric Graphs and Arrangements. Vieweg Press, 2004.
• 13: 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
• 14: Michael T. Goodrich , Roberto Tamassia, Dynamic ray shooting and shortest paths via balanced geodesic triangulations, Proceedings of the ninth annual symposium on Computational geometry, p.318-327, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161157]
• 15: Michael T. Goodrich , Roberto Tamassia, Dynamic Trees and Dynamic Point Location, SIAM Journal on Computing, v.28 n.2, p.612-636, April 1999 [doi>10.1137/S0097539793254376]
• 16: S. Goudsmit. Random distribution of lines in a plane. Rev. Modern Phys., 17:321--322, 1945.
• 17: 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]
• 18: 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]
• 19: Donald E. Knuth, Computer-drawn flowcharts, Communications of the ACM, v.6 n.9, p.555-563, Sept. 1963 [doi>10.1145/367593.367620]
• 20: R. E. Miles. Random polygons determined by random lines in a plane. Proc. Nat. Acad. Sci. U.S.A., 52:901--907, 1964.
• 21: Joseph O'Rourke, Art gallery theorems and algorithms, Oxford University Press, Inc., New York, NY, 1987
• 22: J. Pach. Geometric graph theory. In Surveys in Combinatorics, volume 267 of Lecture Notes Series, pages 167--200. Cambridge University Press, 1999.
• 23: J. Pach. Geometric graph theory. In J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 10, pages 219--238. CRC Press LLC, 2nd edition, 2004.
• 24: J. Pach. Towards a Theory of Geometric Graphs, volume 342 of Contemporary Mathematics. American Mathematical Society, 2004.
• 25: F. P. Preparata. A new approach to planar point location. SIAM J. Comput., 10(3):473--482, 1981.
• 26: F. P. Preparata. Planar point location revisited. Internat. J. Found. Comput. Sci., 1(1):71--86, 1990.
• 27: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 28: 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.
• 29: Neil Sarnak , Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, v.29 n.7, p.669-679, July 1986 [doi>10.1145/6138.6151]
• 30: Robert Sedgewick , Jeffrey Scott Vitter, Shortest paths in Euclidean graphs, Algorithmica, v.1 n.1, p.31-48, Jan. 1986 [doi>10.1007/BF01840435]
• 31: Shang-Hua Teng, Combinatorial aspects of geometric graphs, Computational Geometry: Theory and Applications, v.9 n.4, p.277-287, March 1998 [doi>10.1016/S0925-7721(96)00008-9]
• 32: W. T. Tutte. Convex representations of graphs. Proceedings London Mathematical Society, 10(38):304--320, 1960.
• 33: W. T. Tutte. How to draw a graph. Proceedings London Mathematical Society, 13(52):743--768, 1963.
• 34: 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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

Keywords:
edge crossings, geometric graphs, line transversals, multiscale-dispersed graphs, ray-shooting data structures, road networks