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.