ICS Theory Group

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 Rd. 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.