Short Trees in Polygons

Pawel Winter; Martin Zachariasen; Jens Nielsen

Short Trees in Polygons

Pawel Winter, Martin Zachariasen, Jens Nielsen

Københavns Universitet

Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › peer review

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.

Originalsprog	Engelsk
Tidsskrift	Discrete Applied Mathematics
Vol/bind	118
Sider (fra-til)	55-72
ISSN	0166-218X
Status	Udgivet - 2002
Udgivet eksternt	Ja

Emneord

Computational geometry
Obstacle-avoiding Steiner trees
Heuristics

Citationsformater

@article{db5f45aefb3245e28a37e3e7f0073b4c,

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, Computational geometry, Obstacle-avoiding Steiner trees, Heuristics",

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

year = "2002",

language = "English",

volume = "118",

pages = "55--72",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

}

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

KW - Computational geometry

KW - Obstacle-avoiding Steiner trees

KW - Heuristics

M3 - Journal article

SN - 0166-218X

VL - 118

SP - 55

EP - 72

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Short Trees in Polygons

Abstract

Emneord

Fingeraftryk

Citationsformater