A New Heuristic Constructing Minimal Steiner Trees inside Simple Polygons

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 aminimum Steiner tree in the Euclidean space, the distance between each two edges of which has the least cost. Thisproblem is considered as an NP-hard one. Assuming the simple polygon P with m vertices and n terminals, the purpose of theminimum Steiner tree in the Euclidean space is to connect the nterminals 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

Keywords:

Euclidean Steiner Minimal Tree , Delaunay triangulation , geodesic convex hull