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 journalArticlepeer-review


    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.

    Original languageEnglish (US)
    Pages (from-to)3-31
    Number of pages29
    JournalJournal of Spatial Information Science
    Issue number2011
    StatePublished - 2011


    • Dilation
    • Feed-links
    • Geometric algorithms
    • Network analysis
    • Shortest path

    ASJC Scopus subject areas

    • Information Systems
    • Geography, Planning and Development
    • Computers in Earth Sciences


    Dive into the research topics of 'Connect the dot: Computing feed-links for network extension'. Together they form a unique fingerprint.

    Cite this