Euclidean Steiner trees optimal with respect to swapping 4-point subtrees

Abstract

The Steiner tree problem in Euclidean space E3 asks for a minimum length network T, called a Euclidean Steiner Minimum Tree (ESMT), spanning a given set of points. This problem is NP-hard and the hardness is inherently due to the number of feasible topologies (underlying graph structure of T) which increases exponentially as the number of given points increases. Planarity is a very strong condition that gives a big difference between the ESMT problem in the Euclidean plane E2 and in Euclidean d-space Ed(d ≥ 3): the ESMT problem in the plane is practically solvable whereas the ESMT problem in d-space is really intractable. The simplest tree rearrangement technique is to repeatedly replace a s..