A Sausage Heuristic for Steiner Minimal Trees in Three-Dimensional Euclidean Space |
| |
Authors: | Email author" target="_blank">Badri?ToppurEmail author J?MacGregor?Smith |
| |
Institution: | (1) T.A.Pai Management Institute, Manipal Karnataka, 576104, India;(2) Department of MIE, University of Massachusetts, Amherst, MA 01003, USA |
| |
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 ρ 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(N2). 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 |
本文献已被 SpringerLink 等数据库收录! |
|