ICS Theory Group

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) log2 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.