A Sausage Heuristic for Steiner Minimal Trees in Three-Dimensional Euclidean Space

Authors: Toppur, Badri¹; Smith, J.²

Source: Journal of Mathematical Modelling and Algorithms, Volume 4, Number 2, June 2005 , pp. 199-217(19)

Publisher: Springer

Buy & download fulltext article:

Price: $47.00 plus tax (Refund Policy)

Abstract:

Given a set V of size N

4 vertices in a metric space, how can one interconnect them with the possible use of a set S of size M vertices not in the set V, but in the same metric space, so that the cumulative cost of the inter-connections between all the vertices is a minimum? When one uses the Euclidean metric to compute these inter-connections, this is referred to as the Euclidean Steiner Minimal Tree Problem. This is an NP-hard problem. The Steiner Ratio rho

of a vertex set is the length of this Steiner Minimal Tree (SMT), divided by the length of the Minimum Spanning Tree (MST), and is a popular and tractable measure of solution quality.

The -Sausage heuristic described in this paper employs a decomposition technique to explore the point set. The fixed vertices of the set are connected to a set of centroid vertices of Delaunay tetrahedrons. The path topology is preserved as far as possible, together with a cycle prevention rule, where junctions, and deviations from the -Sausage structure occur. Furthermore, repeated sweeps, with different root vertices are accommodated.

The computational complexity of the heuristic is shown to be O(N²). Experimental results with thousands of vertices are presented. Comparisons with an exponential running time Branch and Bound algorithm are also shown.

Keywords: computational geometry; heuristics

Document Type: Research article

DOI: http://dx.doi.org/10.1007/s10852-004-6390-x

Affiliations: 1: T.A.Pai Management Institute, Manipal Karnataka, 576104, India, Email: tbadri@mail.tapmi.org 2: Department of MIE, University of Massachusetts, Amherst, MA, 01003, USA, Email: jmsmith@ecs.umass.edu

Publication date: 2005-06-01