# ICS 269, Fall 2004: Theory Seminar

## 29 Oct 2004:

Minimum Dilation Stars

David Eppstein and Kevin Wortman

The dilation of a Euclidean graph is defined as the ratio of distance
in the graph divided by distance in *R*^{d}. We consider
the problem of positioning the root of a star such that the dilation
of the resulting graph is minimal. We present a deterministic
*O*(*n* log *n*)-time solution
to the decision problem, as well as a randomized
*O*(*n* log *n*)
expected-time solution to the optimization problem.
The talk will cover selected results from a paper currently under
preparation.