Article ID Journal Published Year Pages File Type
414326 Computational Geometry 2008 13 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics