Steiner hull algorithm for the uniform orientation metrics (Q2479469)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Steiner hull algorithm for the uniform orientation metrics |
scientific article |
Statements
Steiner hull algorithm for the uniform orientation metrics (English)
0 references
26 March 2008
0 references
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.
0 references
computational geometry
0 references
uniform orientation metric
0 references
Steiner tree problem
0 references
Steiner hull
0 references
minimum spanning tree
0 references
algorithm
0 references