Article ID: | iaor19921095 |
Country: | Switzerland |
Volume: | 33 |
Start Page Number: | 577 |
End Page Number: | 599 |
Publication Date: | Nov 1991 |
Journal: | Annals of Operations Research |
Authors: | MacGregor-Smith J., Winter Pawel |
Keywords: | Steiner problem |
The problem of constructing Steiner minimal trees in the Euclidean plane in NP-hard. When in addition obstacles are present, difficulties of constructing obstacle-avoiding Steiner minimal trees are compounded. This problem, which has many obvious practical applications when designing complex transportation and distribution systems, has received very little attention in the literature. The construction of Steiner minimal trees for three terminal points in the Euclidean plane (without obstacles) has been completely solved (among others by Fermat, Torricelli, Cavallieri, Simpson, Heinen) during the span of the last three centuries. This construction is a cornerstone for both exact algorithms and heuristics for the Euclidean Steiner tree problem with arbitrarily many terminal points. An algorithm for three terminal points in the presence of one polygonal convex obstacle is given. It is shown that this algorithm has the worst-case time complexity O(