### Network farthest-point diagrams

#### Abstract

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 *network distance*. Within this metric space, we study farthest points.

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 *G* such that, when given a query point *q* on *G*, we can quickly determine the farthest point(s) from *q* in *G* as well as the farthest distance from *q* in *G*. Furthermore, we introduce a data structure supporting queries for the parts of the network that are farther away from *q* than some threshold *R > 0*, where *R* is part of the query.

We also introduce the *minimum eccentricity feed-link problem* defined as follows. Given a network *G* with geometric edge weights and a point *p* that is not on *G*, connect *p* to a point *q* on *G* with a straight line segment *pq*, called a *feed-link*, such that the largest network distance from *p* 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 *G* is fixed and a query consists of the point *p*.

#### Full Text:

PDFDOI: http://dx.doi.org/10.20382/jocg.v4i1a8

ISSN: 1920-180X