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.