Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1016/S0166-218X(01)00256-6 | Discrete Applied Mathematics |
Keywords | Field | DocType |
computational result,obstacle-avoiding steiner trees,heuristics,short euclidean tree,short tree,computational geometry,linear time,exact algorithm,fast polynomial heuristic,simple polygon,steiner tree,obstacle avoidance | Discrete mathematics,Combinatorics,Polygon,Vertex (geometry),Polynomial,Polygon covering,Steiner tree problem,Computational geometry,Simple polygon,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
118 | 1-2 | Discrete Applied Mathematics |
Citations | PageRank | References |
2 | 0.47 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pawel Winter | 1 | 99 | 12.98 |
| Martin Zachariasen | 2 | 343 | 29.69 |
| Jens Nielsen | 3 | 2 | 0.47 |