A
feed-link is an artificial connection from a given location
p to a real-world network. It is most commonly added to an incomplete network to improve the results of network analysis, by
making
p part of the network. The feed-link has to be “reasonable”, hence we use the concept of dilation to determine the quality
of a connection.
We consider the following abstract problem: Given a simple polygon
P with
n vertices and a point
p inside, determine a point
q on
P such that adding a feedlink
[`(pq)]\overline{pq} minimizes the maximum dilation of any point on
P. Here the
dilation of a point
r on
P is the ratio of the shortest route from
r over
P and
[`(pq)]\overline{pq} to
p, to the Euclidean distance from
r to
p. We solve this problem in
O(
λ
7(
n)log
n) time, where
λ
7(
n) is the slightly superlinear maximum length of a Davenport-Schinzel sequence of order 7. We also show that for convex polygons,
two feed-links are always sufficient and sometimes necessary to realize constant dilation, and that
k feed-links lead to a dilation of 1 +
O(1/
k). For (
α,
β)-covered polygons, a constant number of feed-links suffices to realize constant dilation.
This research has been supported by the Netherlands Organisation for Scientific Research (NWO) under BRICKS/FOCUS grant number
642.065.503, under the project GOGO, and under project no. 639.022.707. B. Aronov has been partially supported by a grant
from the U.S.-Israel Binational Science Foundation, by NSA MSP Grant H98230-06-1-0016, and NSF Grant CCF-08-30691. M. Buchin
is supported by the German Research Foundation (DFG) under grant number BU 2419/1-1.