Open AccessConnect the dot: Computing feed-links for network extension
Author(s) -
Marc van Kreveld,
Boris Aronov,
Kevin Buchin,
Maike Buchin,
Bart M. P. Jansen,
Tom de Jong,
Maarten Löffler,
Jun Luo,
Rodrigo I. Silveira,
Bettina Speckmann
Publication year - 2011
Publication title -
journal of spatial information science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.56
H-Index - 19
ISSN - 1948-660X
DOI - 10.5311/josis.2011.3.47
Subject(s) - face (sociological concept) , connection (principal bundle) , point (geometry) , extension (predicate logic) , combinatorics , lambda , boundary (topology) , mathematics , sequence (biology) , computer science , topology (electrical circuits) , discrete mathematics , geometry , mathematical analysis , physics , social science , sociology , biology , optics , genetics , programming language
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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom