ICS Theory Group

ICS 269, Fall 2005: Theory Seminar

Minimum Dilation Stars in Metric Spaces

Kevin Wortman

October 21, 2005, in CS 259


We consider the following problem: given a collection of n sites separated by distances obeying the triangle inequality, create a star (tree of depth 1) whose root is a new center site and whose leaves are the input sites, such that the dilation of the star is minimal. The problem amounts to computing a weight for each of the n edges from the root to the leaves, such that all the weights in the star obey the triangle inequality. This talk will describe an O(n3)-time algorithm for computing the optimal dilation value, which is a significant component of an algorithm that computes the edge weights.

(Joint work in progress with David Eppstein.)