An Optimal Algorithm for the Euclidean Bottleneck Full Steiner Tree Problem

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.