# Network Farthest-Point Diagrams

arXiv: https://arxiv.org/abs/1304.1909 · HTML: https://mlsanity.com/paper/1304.1909/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Apr 2013.

## Built on by (most cited first, 1 of 1)

- [COL-Trees: Efficient Hierarchical Object Search in Road Networks](https://mlsanity.com/paper/2601.22183/) (2026)

## Abstract (arXiv)

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.