Feed-links for network extensions

ABSTRACT

Road network data is often incomplete, making it hard to perform network analysis. This paper discusses the problem of extending partial road networks with reasonable links, using the concept of dilation (also known as crow flight conversion coefficient). To this end, we study how to connect a point (relevant location) inside a polygon (face of the known part of the road network) to the boundary so that the dilation from that point to any point on the boundary is not too large. We provide algorithms and heuristics, and give a computational and experimental analysis.

REFERENCES

• 1: M. A. Abam , M. de Berg , M. Farshi , J. Gudmundsson, Region-fault tolerant geometric spanners, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1-10, January 07-09, 2007, New Orleans, Louisiana
• 2: P. K. Agarwal, S. Har-Peled, and M. Karia. Computing approximate shortest paths on convex polytopes. Algorithmica, 33(2):227--242, 2002.
• 3: H.-K. Ahn, M. Farshi, C. Knauer, M. H. M. Smid, and Y. Wang. Dilation-optimal edge deletion in polygonal cycles. In Proc. 18th International Symposium on Algorithms and Computation, LNCS 4835, pages 88--99, 2007.
• 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: T. de Jong and T. Tillema. Transport network extensions for accessibility analysis in geographic information systems. In Proceedings Africa GIS 2005, 2005.
• 6: Annette Ebbers-Baumann , Ansgar Grune , Rolf Klein, The Geometric Dilation of Finite Point Sets, Algorithmica, v.44 n.2, p.137-149, February 2006 [doi>10.1007/s00453-005-1203-9]
• 7: Mohammad Farshi , Panos Giannopoulos , Joachim Gudmundsson, Finding the best shortcut in a geometric network, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064143]
• 8: M. Farshi and J. Gudmundsson. Experimental study of geometric t-spanners: A running time comparison. In Proc. Workshop on Experimental Algorithms, LNCS 4525, pages 270--284, 2007.
• 9: 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]
• 10: Stefan Langerman , Pat Morin , Michael A. Soss, Computing the Maximum Detour and Spanning Ratio of Planar Paths, Trees, and Cycles, Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, p.250-261, March 14-16, 2002
• 11: Giri Narasimhan , Michiel Smid, Geometric Spanner Networks, Cambridge University Press, New York, NY, 2007
• 12: 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]
• 13: J. R. Ritsema van Eck. Analyse van Transportnetwerken in GIS voor Sociaal-Geografisch Onderzoek. PhD thesis, Utrecht University, 1993.
• 14: C. Wulff-Nilsen. Computing the dilation of edge-augmented graphs in metric spaces. In Abstr. 24th Europeon Workshop on Computational Geometry, pages 123--126, 2008.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

General Terms:
Algorithms, Experimentation

Keywords:
network analysis, road network