An O(N2) heuristic for steiner minimal trees in E3
James MacGregor Smith, R. Weiss, Minoo Patel · Networks · 1995
Abstract Even though the problem of computing Steiner minimal trees (SMTs) in the plane is well known to be NP‐hard, There exist heuristic algorithms which run in polynomial time. Recent research results have shown that the problem in three dimensions is demonstrably more difficult. This paper approaches the development of a heuristic for the problem utilizing the Delaunay triangulation in 3‐space to compute suboptimal SMTs. Computational results are also provided.