Computer Science – Computational Geometry
Scientific paper
2008-08-27
Computer Science
Computational Geometry
Expanded version of paper appearing at ACM GIS 2008
Scientific paper
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.
Eppstein David
Goodrich Michael T.
No associations
LandOfFree
Studying Geometric Graph Properties of Road Networks Through an Algorithmic Lens does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Studying Geometric Graph Properties of Road Networks Through an Algorithmic Lens, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Studying Geometric Graph Properties of Road Networks Through an Algorithmic Lens will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-529657