Steiner hull algorithm for the uniform orientation metrics

Given a set Z of n<∞ points in the plane and an integer λ⩾2, we consider the problem of finding a λ-Steiner hull of Z, i.e., a region containing every Steiner minimal tree for Z in the λ-metric. We define a λ-Steiner hull λ-SH(Z) of Z 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. A perhaps surprising result is presented, namely that a Euclidean MST for Z can be used to decompose the problem of finding λ-SH(Z) into subproblems. Each of these can then be solved recursively using linear searches combined with a sweep line approach. Using this result, we present an algorithm computing λ-SH(Z). This algorithm has O(λnlogn) running time and O(λn) space requirement which is optimal for constant λ. We prove that λ-SH(Z) is independent of the order of removals of the open wedge-shaped regions.