An Exact Algorithm for the Line-Constrained Bottleneck k-Steiner Tree Problem

In this paper, we address the line-constrained bottleneck k-Steiner tree (LcBkStT) problem. Specifically, given an input line l, a set P of n points in \(\mathbb {R}^2\) and a positive integer k, we are asked to find at most k Steiner points located on this line l and additionally a spanning tree \(T_l\) on these \(n+k\) points, the objective is to minimize the length of the longest edge in \(T_l\) , where the edges in \(T_l\) are not allowed to cross this line l and the length of each edge in \(T_l\) is equal 0 if the two endpoints of that edge are located on the aforementioned line l. Using a technique of oriented Voronoi diagram, we design an exact algorithm for the LcBkStT problem in \(O(n \log n + f(k)\cdot n^k)\) time, where f(k) is a function dependent only on the positive integer k. This algorithm is an exact algorithm for the LcB1StT problem (for \(k=1\) ) in \(O(n \log n)\) time.