| Summary: | <p>Consider the continuum of points along the edges of a network, i.e., an undirected graph with positive edge weights. We measure distance between these points in terms of the shortest path distance along the network, known as the <em>network distance</em>. Within this metric space, we study farthest points.</p><p>We introduce network farthest-point diagrams, which capture how the farthest points---and the distance to them---change as we traverse the network. We preprocess a network <em>G</em> such that, when given a query point <em>q</em> on <em>G</em>, we can quickly determine the farthest point(s) from <em>q</em> in <em>G</em> as well as the farthest distance from <em>q</em> in <em>G</em>. Furthermore, we introduce a data structure supporting queries for the parts of the network that are farther away from <em>q</em> than some threshold <em>R > 0</em>, where <em>R</em> is part of the query.</p><p>We also introduce the <em>minimum eccentricity feed-link problem</em> defined as follows. Given a network <em>G</em> with geometric edge weights and a point <em>p</em> that is not on <em>G</em>, connect <em>p</em> to a point <em>q</em> on <em>G</em> with a straight line segment <em>pq</em>, called a <em>feed-link</em>, such that the largest network distance from <em>p</em> to any point in the resulting network is minimized. We solve the minimum eccentricity feed-link problem using eccentricity diagrams. In addition, we provide a data structure for the query version, where the network <em>G</em> is fixed and a query consists of the point <em>p</em>.</p>
|
|---|