Steiner hull algorithm for the uniform orientation metrics

DOI10.1016/J.COMGEO.2007.10.002MaRDI QIDQ2479469zbMATH OpenOpenAlexFDO

Authors Christian Wulff-Nilsen

Publication date 26 March 2008

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2007.10.002

zbMATH Keywords

algorithmcomputational geometryminimum spanning treeSteiner hullSteiner tree problemuniform orientation metric

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Review text

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.

Recommendations

• Steiner trees for fixed orientation metrics
• The Steiner tree problem in orientation metrics
• Optimal Steiner hull algorithm
• Rotational Steiner Ratio Problem Under Uniform Orientation Metrics
• Canonical forms and algorithms for Steiner trees in uniform orientation metrics
• A tight lower bound for Steiner orientation
• An algorithm for the steiner problem in the euclidean plane
• A tight lower bound for planar Steiner orientation
• Algorithms and Computation
• Flexibility of Steiner trees in uniform orientation metrics

Cites work

• Canonical forms and algorithms for Steiner trees in uniform orientation metrics
• scientific article; zbMATH DE number 750011 (Why is no real title available?)
• Minimum networks in uniform orientation metrics
• On finding the convex hull of a simple polygon
• Optimal Steiner hull algorithm
• The Steiner tree problem

Cited in

(3)

• Quasi-median hulls in Hamming space are Steiner hulls
• Optimal Steiner hull algorithm
• scientific article; zbMATH DE number 2044913 (Why is no real title available?)

This page was built for publication: Steiner hull algorithm for the uniform orientation metrics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2479469)