A New Heuristic Algorithm for Constructing Steiner Trees inside Simple polygons in Presence of Obstacles

Steiner tree problem leads to solutions in several scientific and business contexts, including computer networks routing and electronic integrated circuits. Computing fields of this problemhas become an important research topic in computational geometry. Considering the number of points in the Euclideanplane, called terminal points, a minimum spanning tree is obtained which connects these points. A series of other points (Steiner points) are added to the tree, which makes it shorter in length. The resulting tree is called Euclidean Steiner minimal tree. It is considered as an NP-hard problem. Considering asimple polygon P with m vertices and n terminals, in which you are trying to find a Euclidean Steiner tree that is connected to alln terminals existing inside p. In this paper we propose a solution for several terminals in a simple polygonal in presence of obstacles.

کلیدواژه ها:

Euclidean Steiner Minimal Tree ، Straight skeleton of simple polygon ، geodesic convex hull