Connect the dot: Computing feed-links for network extension

Journal of Spatial Information Science

卷:2011

Maike Buchin¹  Rodrigo I. Silveira¹  Kevin Buchin¹  Tom de Jong¹  Bart Jansen¹  Bettina Speckmann¹  Jun Luo¹  Maarten Loffler¹  Boris Aronov²  Marc van Kreveld³ 

[1] ;

[2] Polytechnic Institute of NYU;

[3] Utrecht University;

关键词: network analysis;    geometric algorithms;    feed-links;    shortest path;    dilation;   

DOI  :  10.5311/JOSIS.2011.3.47

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown