Minimum Dilation Stars
<|reference_start|>Minimum Dilation Stars: The dilation of a Euclidean graph is defined as the ratio of distance in the graph divided by distance in R^d. In this paper we consider the problem of positioning the root of a star such that the dilation of the resulting star is minimal. We present a deterministic O(n log n)-time algorithm for evaluating the dilation of a given star; a randomized O(n log n) expected-time algorithm for finding an optimal center in R^d; and for the case d=2, a randomized O(n 2^(alpha(n)) log^2 n) expected-time algorithm for finding an optimal center among the input points.<|reference_end|>
@article{eppstein2004minimum,
    title={Minimum Dilation Stars},
    author={David Eppstein and Kevin A. Wortman},
    journal={Comp. Geom. Theory and Appl. 37(1):27-37, 2007},
    year={2004},
    doi={10.1016/j.comgeo.2006.05.007},
    archivePrefix={arXiv},
    eprint={cs/0412025},
    primaryClass={cs.CG}
}