A New Heuristic Constructing Minimal Steiner Trees inside Simple Polygons

Abstract

The Steiner tree problem has numerous applications in urban transportation network, design of electronic integrated circuits, and computer network routing. This problem aims at finding a minimum Steiner tree in the Euclidean space, the distance between each two edges of which has the least cost. This problem is considered as an NP-hard one. Assuming the simple polygon P with m vertices and n terminals, the purpose of the minimum Steiner tree in the Euclidean space is to connect the n terminals existing in p. In the proposed algorithm, obtaining optimal responses will be sought by turning this problem into the Steiner tree problem on a graph.