A heuristic algorithm for Euclidean Steiner Minimal Tree inside simple polygon

The Steiner problem leads to solutions in several scientific and business applications. Computer networks routing and electronic integrated circuits are few examples of it. Assuming some points in the Euclidean plane, we can construct a minimum spanning tree connecting these (terminal) nodes. It is possible to add some extra points (Steiner Points) in order to decrease the length of this tree, which would in turn lead to Euclidean Steiner Minimal Tree (ESMT). This problem is considered as a NP-hard problem, as it may contain some nodes that are not in the set of given nodes. Assuming a simple polygon P with m vertices and n terminals in it, we try to find an Euclidean Steiner minimal tree connecting all these n terminals in P. In this paper, we propose a new solution based on the straight skeleton of a simple polygon for finding Euclidean Steiner tree of any number of terminals, in a given simple polygon.