## ICS 269, Fall 2005: Theory Seminar

# Minimum Dilation Stars in Metric Spaces

## Kevin Wortman

### October 21, 2005, in CS 259

Abstract:

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(*n*^{3})-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.)