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

Vahid Khosravinejad, Alireza Bagheri, Alireza Khosravinejad

Abstract


Steiner tree problem leads to solutions in several scientific and business contexts, including computer networks routing and electronic integrated circuits. Computing fields of this problem has become an important research topic in computational geometry. Considering the number of points in the Euclidean plane, 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 a simple polygon P with m vertices and n terminals, in which you are trying to find a Euclidean Steiner tree that is connected to all n terminals existing inside p. In this paper we propose a solution for several terminals in a simple polygonal in presence of obstacles.

Keywords


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

Full Text:

PDF


Lululemon Black Friday cheap nfl jerseys Lululemon factory Outlet ny Black Friday discount tiffany outlet wholesale soccer jerseys online oakley black friday cheap nhl jerseys china cheap nfl jerseys north face black friday sale cheap nfl jerseys online Jordans Black Friday Sale 2015 Cheap Moncler Cyber Monday moncler outlet cheap soccer jerseys moncler outlet black friday cheap authentic nfl jerseys north face cyber monday Louboutin Black Friday canada wholesale cheap nfl jerseys lululemon cyber monday 2015 cheap nfl jerseys from china 2015 Cheap Moncler Black Friday Sale Moncler Cyber Monday 2015 cheap jerseys Lululemon Cyber Monday Sale jordans cyber monday deals 2015 cheap nike nfl jerseys Black Friday deals Lululemon 2015 jordan black friday 2015 Moncler Jackets Black Friday Sale 2015 Louboutin Pas Cher Black Friday 2015 Canada Lululemon north face black friday cheap wholesale soccer jerseys