Steiner hull algorithm for the uniform orientation metrics (Q2479469)

Let \(Z\) be a finite set of points in the plane and an integer \(\lambda \geq 2\). The \(\lambda\)-Steiner hull \(\lambda\)-\(SH(Z)\) of \(Z\) is defined as a set obtained by a maximal sequence of removals of certain open wedge-shaped regions from an initial hull followed by a simplification of its boundary. The author shows that an Euclidean minimum spanning tree for \(Z\) can be used to decompose the problem of finding the \(\lambda\)-\(SH(Z)\) into subproblems. Each of these can be solved recursively using linear searches combined with a sweep line approach. As a consequence of this result, an algorithm computing the \(\lambda\)-\(SH(Z)\) is presented. The algorithm has \({\mathcal O}(\lambda n \log n)\) running time and \({\mathcal O}(\lambda n)\) space requirements (\(n\) is the number of terminals) which is optimal for \(\lambda\). Finally, the author proves that the \(\lambda\)-\(SH(Z)\) is uniquely defined in the sense that it does not depend on the chosen maximal sequence of removals of open wedge-shaped regions.