Minimum dilation stars
- Author(s): Eppstein, David
- Wortman, Kevin A.
- et al.
Published Web Locationhttp://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TYS-4M0J4GX-1&_user=4422&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000059600&_version=1&_urlVersion=0&_userid=4422&md5=f629b048c21879c236c68d228a07786c
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(n2(alpha(n)) log(2) n) expected-time algorithm for finding an optimal center among the input points.