Skip to main content
Open Access Publications from the University of California

UC Irvine

UC Irvine Previously Published Works bannerUC Irvine

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(n2(alpha(n)) log(2) n) expected-time algorithm for finding an optimal center among the input points.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View