Computer Science – Computational Geometry
Scientific paper
2009-09-15
Computer Science
Computational Geometry
Fuller version of paper appearing in ACM GIS '09
Scientific paper
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(sqrt(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(sqrt(n) log n) expected time. Finally, we provide empirical justification for this claim as well.
Eppstein David
Goodrich Michael T.
Trott Lowell
No associations
LandOfFree
Going Off-road: Transversal Complexity in Road Networks 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 Going Off-road: Transversal Complexity in Road Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Going Off-road: Transversal Complexity in Road Networks will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-581946