Řešení Steinerova problému v euklidovské rovině s využitím geometrických struktur

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F08%3APU76870" target="_blank" >RIV/00216305:26210/08:PU76870 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Solving the Euclidean Steiner Tree Problem Using Geometric Structures

Popis výsledku v původním jazyce

The Euclidean Steiner Tree Problem is to find a shortest network spanning a set of fixed points in the plane, allowing the addition of auxiliary points to the set. The problem being NP-hard, polynomial-time approximations or heuristics are required. There are many rather complex heuristics based, e.g., on enumerating full topologies and consuming long time for computations for large instances. In this paper, we applied to use tools of computational geometry, especially the properties of Delaunay triangulation, a well-known geometric structure, and combine them with insertion heuristics based on the construction of the Euclidean minimum spanning tree. Thus an algorithm could be proposed that is very efficient and fast. Experiments confirmed that computations by this algorithm generate very good results in a reasonable amount of time, even for large instances of the studied problem.

Název v anglickém jazyce

Solving the Euclidean Steiner Tree Problem Using Geometric Structures

Popis výsledku anglicky

The Euclidean Steiner Tree Problem is to find a shortest network spanning a set of fixed points in the plane, allowing the addition of auxiliary points to the set. The problem being NP-hard, polynomial-time approximations or heuristics are required. There are many rather complex heuristics based, e.g., on enumerating full topologies and consuming long time for computations for large instances. In this paper, we applied to use tools of computational geometry, especially the properties of Delaunay triangulation, a well-known geometric structure, and combine them with insertion heuristics based on the construction of the Euclidean minimum spanning tree. Thus an algorithm could be proposed that is very efficient and fast. Experiments confirmed that computations by this algorithm generate very good results in a reasonable amount of time, even for large instances of the studied problem.

Druh

D - Stať ve sborníku

CEP obor

BB - Aplikovaná statistika, operační výzkum

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2008

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the 14th International Conference on Soft Computing MENDEL 2008

ISBN

978-80-214-3675-6

ISSN

—

e-ISSN

—

Počet stran výsledku

8

Strana od-do

—

Název nakladatele

BUT FME

Místo vydání

Brno

Místo konání akce

Brno University of Technology

Datum konání akce

18. 6. 2008

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—