Michiel Smid

Let *P* and *S* be two disjoint sets of *n* and *m* points in the plane,
respectively. We consider the problem of computing a Steiner tree whose
Steiner vertices belong to *S*, in which each point of *P* is a leaf,
and whose longest edge length is minimum. We present an algorithm that
computes such a tree in O((n+m) log m) time, improving the previously
best result by a logarithmic factor. We also prove a matching lower
bound in the algebraic computation tree model.

Joint work with Ahmad and Anil.