The difficulty of straight edge and compass solutions to the Euclidean Steiner Minimal Tree Problem for more than three vertices, has been known for at least three centuries. Analytic geometry methods, in addition to these tools, use Algebra and Cartesian frames of reference. In E2, optimal solutions can be achieved for 10,000 points and more. For more than ten vertices in E 3 or higher dimensions, these exact formulations have proved difficult and cumbersome from the point of view of an algorithmic solution. A discrete version of the problem was shown to be NP-complete in 1977. Decomposition heuristics based on Computational Geometry were suggested, for these larger point sets. The thesis features a literature review of the considerable research efforts on the Steiner problem in two and three dimensional space, with the Euclidean metric. Heuristics of polynomial complexity, that have proven satisfactory for large point sets are considered after the O.R. methods that are of exponential order. The Steiner Ratio ρ of a vertex set is the length of the Steiner Minimal Tree (SMT), divided by the length of the Minimum Spanning Tree (MST), and in addition to execution time, is a key measure of performance, of algorithms and heuristics devoted to this problem. The consideration and comparison of the performance of algorithms, leads to the issue of the best Steiner ratio for a particular space. The d-Sausage, an unending geometric arrangement of regular simplices, has yielded the best Steiner Ratio in three and higher dimensional Euclidean space. A particular Full Steiner Tree topology, which we refer to as the path topology, is proven to be the optimal topology, for the d-Sausage when d = 1 or 2. Other structural properties of the flat sausage and the [special characters omitted]-Sausage, as these two instances of the d-Sausage are referred to, are proved as lemmas and theorems. This theoretical framework serves as a foundation for a heuristic for finding SMTs for the very large point sets. The sausage has been shown to have a superior Steiner ratio compared to a simplex. For this reason it is the preferred primitive for a decomposition technique. Finally, the ties between the Steiner Minimal Tree Problem, and the Euclidean Graph Embedding Problem, are explored in the light of the Minimum Energy Configuration of molecules, and Maxwell's theorem.
| Identifer | oai:union.ndltd.org:UMASS/oai:scholarworks.umass.edu:dissertations-3607 |
| Date | 01 January 2002 |
| Creators | Badri, Toppur N |
| Publisher | ScholarWorks@UMass Amherst |
| Source Sets | University of Massachusetts, Amherst |
| Language | English |
| Detected Language | English |
| Type | text |
| Source | Doctoral Dissertations Available from Proquest |
Page generated in 0.0024 seconds