MSc Thesis Defense: Finding Steiner Minimal Trees in Euclidean d-Space – University of Copenhagen

MSc Thesis Defense: Finding Steiner Minimal Trees in Euclidean d-Space

MSc Thesis Defense by Jens Fredskov.

Supervisor: Pawel Winter
Censor: Jesper Larsen, DTU

Abstract

This thesis presents possible improvements to the original implementation of the algorithm for finding Steiner minimal trees proposed by Smith [1]. The suggested changes include a new data structure and method for building topologies as well as a method for ordering the terminals before the topologies. This is used to avoid double-work in the original implementation which rebuilds the entire tree every time its topology changes.

This the thesis also presents a simple iteration for optimizing full Steiner trees as an alternative to the one proposed by Smith [1]. This includes presenting an analytical solution to the Fermat-Torricelli problem as proposed by Uteshev [2] and further generalizing it from 2D to higher dimensions.

The thesis also presents experimental work performed to test the correctness and efficiency (compared to the original implementation) of the new implementation. The new suggested iteration, based on the analytical solution, shows some sub-optimal results. These are discussed and further investigated, and are concluded to probably stem from the used error-function and the if-clauses deciding when to prune a topology. A possible way of fixing the sub-optimality is then proposed.

With the sub-optimality in mind, the new simple iteration however seems to show promise as the performance of it in general is much better than the original implementation using Smith's iteration. The new implementation of Smith's iteration show performance equivalent to the original implementation. This however is ascribed to the choice of programming language, and the much larger amount of trees the new implementation optimizes before reaching optimality. The new method for ordering terminals shows very promising results (when used with either of the iterations).

Finally the thesis presents and discusses possible extensions and improvements to the new implementation.

[1] Smith, W. D. (1992). How to find Steiner minimal trees in euclideand-space. Algorithmica, 7(1-6), 137-177.
[2] Uteshev, A. Y. (2014). Analytical solution for the generalized Fermat–Torricelli problem. The American Mathematical Monthly, 121(4), 318-331.