Towards an Understanding of Euclidean Steiner Networks

Abstract

The classical Steiner tree problem is the geometric problem of constructing the shortest length network interconnecting a given set of points (terminals) and possibly extra points (Steiner points) in the Euclidean plane. It is a valuable tool that has been used to find optimal short networks in many important applications. In this thesis, we develop a theory for locally minimal length networks that connect a given set of terminals. This involves examining a generalisation of Steiner trees that are called Euclidean Steiner networks (ESN). We introduce examples of ESNs and we suggest several new results and conjectures inspired from these examples, such as the minimum number of terminals to get a nontrivial ESN. The GeoSteiner 5.3 package does not support ESNs with cycles despite being a helpful numerical technique for determining the Steiner minimum tree. We present computational results on ESNs, using the package GeoSteiner 5.3 to produce a list of full Steiner trees (FSTs). We create a Matlab tool to find all possible ESNs for a given set of terminals from a given list of FSTs. We also study the properties of the set of ESNs, particularly the distribution of lengths depending on various conditions, such as the existence of the cycle. As an application, we apply this method to understand better the structure of Endoplasmic Reticulum (ER) networks that have been observed in plant cells. We can generate ESNs that are more similar to abstracted ER networks and quantify how they are generally connected and structured.