Short Trees in Polygons

Pawel Winter; Martin Zachariasen; Jens Nielsen

doi:10.1016/S0166-218X(01)00256-6

Short Trees in Polygons

Pawel Winter, Martin Zachariasen, Jens Nielsen

Náttúruvísindadeildin - Faculty of Science and Technology

Research output: Contribution to journal › Article › peer-review

13 Citations (Scopus)

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.

Original language	English
Pages (from-to)	55-72
Number of pages	18
Journal	Discrete Applied Mathematics
Volume	118
Issue number	1-2
DOIs	https://doi.org/10.1016/S0166-218X(01)00256-6
Publication status	Published - 2002

Keywords

computational geometry
obstacle-avoiding steiner trees
heuristics

Access to Document

10.1016/S0166-218X(01)00256-6

Cite this

@article{381b7855c57d413b9fffbd97f39b8f57,

title = "Short Trees in Polygons",

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.",

keywords = "computational geometry, obstacle-avoiding steiner trees, heuristics",

author = "Pawel Winter and Martin Zachariasen and Jens Nielsen",

year = "2002",

doi = "10.1016/S0166-218X(01)00256-6",

language = "English",

volume = "118",

pages = "55--72",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "1-2",

}

TY - JOUR

T1 - Short Trees in Polygons

AU - Winter, Pawel

AU - Zachariasen, Martin

AU - Nielsen, Jens

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

KW - computational geometry

KW - obstacle-avoiding steiner trees

KW - heuristics

U2 - 10.1016/S0166-218X(01)00256-6

DO - 10.1016/S0166-218X(01)00256-6

M3 - Article

SN - 0166-218X

VL - 118

SP - 55

EP - 72

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1-2

ER -

Short Trees in Polygons

Abstract

Keywords

Access to Document

Fingerprint

Cite this