# ICS 269, Spring 2005: Theory Seminar

## 18 Feb 2005:

Minimum Dilation Stars, part two: the constrained case.

Speaker: Kevin Wortman

We consider the problem of selecting a point c to serve as the root of a
star with minimal dilation for a given set of n leaves. In a prior talk
we presented an O(n log n) expected-time algorithm for the case when d
is a fixed constant and c is not required to be one of the input points.
In this talk we consider the case when d=2 and c is constrained to be
one of the input points. We present an O(n 2^{α(n)} log^{2} n)
expected-time solution to this problem, which uses the algorithm for the
unconstrained case as a component.

This is a joint work of David Eppstein and Kevin Wortman.