On Exact Solutions to the Euclidean Bottleneck Steiner Tree Problem

We study the Euclidean bottleneck Steiner tree problem: given a set P of n points in the Euclidean plane, called terminals, find a Steiner tree with at most k Steiner points such that the length of the longest edge in the tree is minimized. This problem is known to be NP-hard even to approximate within ratio root 2.. We focus on finding exact solutions to the problem for a small constant k. Based on geometric properties of optimal location of Steiner points, we present an 0(n log n) time exact algorithm for k = 1 and an O(n(2)) time algorithm for k = 2. Also, we present an O(n log n) time exact algorithm to the problem for a special case where there is no edge between Steiner points.