A sausage heuristic for Steiner minimal trees in three-dimensional Euclidean space

DOI10.1007/s10852-004-6390-xzbMath1093.90095OpenAlexW1983276997MaRDI QIDQ814961

Badri Toppur, James MacGregor Smith

Publication date: 8 February 2006

Published in: JMMA. Journal of Mathematical Modelling and Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10852-004-6390-x

zbMATH Keywords

heuristicscomputational geometry

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Geometry-experiment algorithm for Steiner minimal tree problem ⋮ An evolutionary design of weighted minimum networks for four points in the three-dimensional Euclidean space ⋮ A randomized Delaunay triangulation heuristic for the Euclidean Steiner tree problem in \(\Re ^{d }\)

Uses Software

• Qhull
• FindSteinerTree
• Voronoi

Cites Work

• On the shortest spanning subtree of a graph and the traveling salesman problem
• A proof of the Gilbert-Pollak conjecture on the Steiner ratio
• How to find Steiner minimal trees in Euclidean \(d\)-space
• On the Steiner ratio in 3-space
• Disproofs of generalized Gilbert-Pollak conjecture on the Steiner ratio in three or more dimensions
• On the Problem of Steiner
• Steiner problem in networks: A survey
• The Complexity of Computing Steiner Minimal Trees
• The quickhull algorithm for convex hulls
• An O(N²) heuristic for steiner minimal trees in E³
• Steiner Minimal Trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A sausage heuristic for Steiner minimal trees in three-dimensional Euclidean space