20121201
On farthestpoint information in networks
Publication
Publication
Consider the continuum of points along the edges of a network, an embedded undirected graph with positive edge weights. Distance between these points can be measured as shortest path distance along the edges of the network. We introduce two new concepts to capture farthestpoint information in this metric space. The first, eccentricity diagrams, are used to encode the distance towards farthest points for any point on the network compactly. With this, we can solve the minimum eccentricity feedlink problem, i.e., the problem to extend a network by one new point minimizing the largest network distance towards the new point. The second, network farthestpoint diagrams, provide an implicit description of the sets of farthest points. A network farthestpoint diagram is, in principle, a compressed farthestpoint network Voronoi link diagram generated by the entire continuum of uncountably many points on the network at hand. We provide construction algorithms for data structures that allow for queries for the distance to farthest points as well as their location from any point on a network in optimal time. Thus, we establish first bounds on construction times and storage requirements of such data structures.
Additional Metadata  

Conference  24th Canadian Conference on Computational Geometry, CCCG 2012 
Citation 
Bose, P, De Carufel, J.L. (JeanLou), Grimm, C. (Carsten), Maheshwari, A, & Smid, M. (2012). On farthestpoint information in networks. Presented at the 24th Canadian Conference on Computational Geometry, CCCG 2012.
