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

Minimum dilation stars

  • Author(s): Eppstein, David
  • Wortman, Kevin A.
  • et al.
Abstract

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 Academic Senate's Open Access Policy. Let us know how this access is important for you.

Main Content
Current View