Premium
An O(N 2 ) heuristic for steiner minimal trees in E 3
Author(s) -
Smith J. MacGregor,
Weiss Rich,
Patel Minoo
Publication year - 1995
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230260411
Subject(s) - steiner tree problem , delaunay triangulation , heuristic , combinatorics , mathematics , computer science , time complexity , triangulation , discrete mathematics , mathematical optimization , geometry
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.