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)logm) time, improving the previously best result by a logarithmic factor. We also prove a matching lower bound in the algebraic computation tree model.

Additional Metadata
Keywords Bottleneck length, Minimum spanning tree, Steiner tree, Yao graph
Persistent URL dx.doi.org/10.1016/j.comgeo.2013.10.001
Journal Computational Geometry
Citation
Biniaz, A. (Ahmad), Maheshwari, A, & Smid, M. (2014). An optimal algorithm for the Euclidean bottleneck full Steiner tree problem. Computational Geometry, 47(3 PART A), 377–380. doi:10.1016/j.comgeo.2013.10.001