Short trees in polygons Original Research Article

We consider the problem of determining a short Euclidean tree spanning a number of terminals in a simple polygon. First of all, linear time (in the number of vertices of the polygon) exact algorithms for this problem with three and four terminals are given. Next, these algorithms are used in a fast polynomial heuristic based on the concatenation of trees for appropriately selected subsets with up to four terminals. Computational results indicate that the solutions obtained are close to optimal solutions.