Connect the Dot: Computing Feed-links for Network Extension
Road network analysis can require distance from points that are not on the network themselves. We study the algorithmic problem of connecting a point inside a face (region) of the road network to its boundary while minimizing the detour factor of that point to any point on the boundary of the face. We show that the optimal single connection (feed-link) can be computed in O(lambda_7(n) log n) time, where n is the number of vertices that bounds the face and lambda_7(n) is the slightly superlinear maximum length of a Davenport-Schinzel sequence of order 7 on n symbols. We also present approximation results for placing more feed-links, deal with the case that there are obstacles in the face of the road network that contains the point to be connected, and present various related results.
, keywords: Computational Geometry, Geographical Information Analysis, Graphs Theory
Journal Article (peer-reviewed)
Bart Jansen, Bettina Speckmann, Boris Aronov, Jun Luo, Kevin Buchin, Maarten Löffler, Maike Buchin, Marc van Kreveld, Rodrigo I. Silveira, Tom de Jong
Connect the Dot: Computing Feed-links for Network Extension
Journal of Spatial Information Science
3, 3–31, 2011
Conference Proceedings (peer-reviewed)
Bettina Speckmann, Boris Aronov, Jun Luo, Kevin Buchin, Maarten Löffler, Maike Buchin, Marc van Kreveld, Rodrigo I. Silveira
Connect the Dot: Computing Feed-links with Minimum Dilation
Proc. 11th Algorithms and Data Structures Symposium
LNCS 5664, 49–60, 2009
Conference Proceedings (peer-reviewed)
Bart Jansen, Bettina Speckmann, Boris Aronov, Jun Luo, Kevin Buchin, Maarten Löffler, Maike Buchin, Marc van Kreveld, Rodrigo I. Silveira, Tom de Jong
Feed-links for Network Extensions
Proc. 16th ACM International Conference on Advances in Geographic Information Systems
308–316, 2008
back to list
