Steiner hull algorithm for the uniform orientation metrics (Q2479469): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Minimum Networks in Uniform Orientation Metrics / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Canonical forms and algorithms for Steiner trees in uniform orientation metrics / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Steiner tree problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4764186 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On finding the convex hull of a simple polygon / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Optimal Steiner hull algorithm / rank | |||
Normal rank |
Latest revision as of 20:14, 27 June 2024
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