Short Trees in Polygons

Pawel Winter, Martin Zachariasen, Jens Nielsen

Research output: Contribution to journalArticlepeer-review

13 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)55-72
Number of pages18
JournalDiscrete Applied Mathematics
Issue number1-2
Publication statusPublished - 2002


  • computational geometry
  • obstacle-avoiding steiner trees
  • heuristics


Dive into the research topics of 'Short Trees in Polygons'. Together they form a unique fingerprint.

Cite this