Connect the dot: Computing feed-links for network extension

Boris Aronov; Kevin Buchin; Maike Buchin; Bart Jansen; Tom de Jong; Marc van Kreveld; Maarten Löffler; Jun Luo; Rodrigo I. Silveira; Bettina Speckmann

doi:10.5311/JOSIS.2011.3.47

Connect the dot: Computing feed-links for network extension

Boris Aronov, Kevin Buchin, Maike Buchin, Bart Jansen, Tom de Jong, Marc van Kreveld, Maarten Löffler, Jun Luo, Rodrigo I. Silveira, Bettina Speckmann

Research output: Contribution to journal › Article › peer-review

Abstract

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(λ₇(n) log n) time, where n is the number of vertices that bounds the face and λ₇(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.

Original language	English (US)
Pages (from-to)	3-31
Number of pages	29
Journal	Journal of Spatial Information Science
Volume	3
Issue number	2011
DOIs	https://doi.org/10.5311/JOSIS.2011.3.47
State	Published - 2011

Keywords

Dilation
Feed-links
Geometric algorithms
Network analysis
Shortest path

ASJC Scopus subject areas

Information Systems
Geography, Planning and Development
Computers in Earth Sciences

Access to Document

10.5311/JOSIS.2011.3.47

Cite this

@article{954061f8169143afad2da81dfab78ebd,

title = "Connect the dot: Computing feed-links for network extension",

abstract = "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(λ7(n) log n) time, where n is the number of vertices that bounds the face and λ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 = "Dilation, Feed-links, Geometric algorithms, Network analysis, Shortest path",

author = "Boris Aronov and Kevin Buchin and Maike Buchin and Bart Jansen and {de Jong}, Tom and {van Kreveld}, Marc and Maarten L{\"o}ffler and Jun Luo and Silveira, {Rodrigo I.} and Bettina Speckmann",

note = "Publisher Copyright: {\textcopyright} By the author(s).",

year = "2011",

doi = "10.5311/JOSIS.2011.3.47",

language = "English (US)",

volume = "3",

pages = "3--31",

journal = "Journal of Spatial Information Science",

issn = "1948-660X",

publisher = "The National Center for Geographic Information and Analysis (NCGIA)",

number = "2011",

}

TY - JOUR

T1 - Connect the dot

T2 - Computing feed-links for network extension

AU - Aronov, Boris

AU - Buchin, Kevin

AU - Buchin, Maike

AU - Jansen, Bart

AU - de Jong, Tom

AU - van Kreveld, Marc

AU - Löffler, Maarten

AU - Luo, Jun

AU - Silveira, Rodrigo I.

AU - Speckmann, Bettina

N1 - Publisher Copyright: © By the author(s).

PY - 2011

Y1 - 2011

N2 - 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(λ7(n) log n) time, where n is the number of vertices that bounds the face and λ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.

AB - 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(λ7(n) log n) time, where n is the number of vertices that bounds the face and λ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.

KW - Dilation

KW - Feed-links

KW - Geometric algorithms

KW - Network analysis

KW - Shortest path

UR - http://www.scopus.com/inward/record.url?scp=84882989300&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84882989300&partnerID=8YFLogxK

U2 - 10.5311/JOSIS.2011.3.47

DO - 10.5311/JOSIS.2011.3.47

M3 - Article

AN - SCOPUS:84882989300

SN - 1948-660X

VL - 3

SP - 3

EP - 31

JO - Journal of Spatial Information Science

JF - Journal of Spatial Information Science

IS - 2011

ER -

Connect the dot: Computing feed-links for network extension

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this