Steiner minimal trees in three-dimensional Euclidean space

2002 2002

Other formats: Order a copy

Abstract (summary)

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.

Indexing (details)

Operations research;
0796: Operations research
0405: Mathematics
Identifier / keyword
Applied sciences; Pure sciences; Euclidean space; Steiner minimal trees; Three-dimensional
Steiner minimal trees in three-dimensional Euclidean space
Badri, Toppur N.
Number of pages
Publication year
Degree date
School code
DAI-B 63/01, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
0493525564, 9780493525563
Smith, J. MacGregor
University of Massachusetts Amherst
University location
United States -- Massachusetts
Source type
Dissertations & Theses
Document type
Dissertation/thesis number
ProQuest document ID
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.