Minimum dilation stars

We consider variants of the minimum dilation star problem. In this problem, given a set of sites drawn from some space, an algorithm must develop a star-topology network spanning all the sites, such that the center node meets certain criteria and the dilation of the network is minimal.;The dilation of two vertices in any embedded graph is the ratio of their distance through the graph, divided by the direct distance between the sites in the ambient space. The dilation of the entire graph is the largest dilation among any of its vertices. Dilation is a fair measure of the quality of a network; in the application domain of transportation networks, it corresponds to the multiplicative slow-down factor imposed on travelers constrained to travel within the network. As such, algorithms for constructing low dilation graphs may find applications to operational planning problems.;Our core findings are efficient algorithms for solving four variants on the minimum dilation star problem: (1) find the optimal center in Euclidean space; (2) find the optimal center among the input sites, in the Euclidean plane; (3) find an approximately-optimal center among the input sites, in Euclidean space; (4) and, find the optimal center in an abstract metric space.;As means to these ends, we also give algorithms for evaluating the dilation of a star in Euclidean space, and solving a variant of the parametric negative cycle detection problem.