Konstrukce 2D zobecněného Voroného diagramu, část I: Aproximační algoritmus

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F06%3APU65945" target="_blank" >RIV/00216305:26210/06:PU65945 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

A Construction of the 2D Generalized Voronoi Diagram, Part I: An Approximation Algorithm

Popis výsledku v původním jazyce

This paper proposes a new approximation algorithm for constructing the Generalized Voronoi diagram (GVD) for point, line, or polygonal generators based on Fortune?s plane sweep technique. The algorithm approximates a line generator or polygonal edge generators by a sequence of point generator with a given precision. This approach attempts to detect edges of narrow corridors, which are approximated with more points than others, thereby the computation is faster than in case of the uniform distribution with the same precision in these narrow corridors. The worst-time complexity of the computation is O(n log n), where n is the number of approximation point generators. This approximation algorithm is suitable for generating the GVD serving as a base for sampling-based robot motion planning methods, especially for robots with many degrees of freedom, by assuring the maximal clearance distance from surrounding obstacles.

Název v anglickém jazyce

A Construction of the 2D Generalized Voronoi Diagram, Part I: An Approximation Algorithm

Popis výsledku anglicky

This paper proposes a new approximation algorithm for constructing the Generalized Voronoi diagram (GVD) for point, line, or polygonal generators based on Fortune?s plane sweep technique. The algorithm approximates a line generator or polygonal edge generators by a sequence of point generator with a given precision. This approach attempts to detect edges of narrow corridors, which are approximated with more points than others, thereby the computation is faster than in case of the uniform distribution with the same precision in these narrow corridors. The worst-time complexity of the computation is O(n log n), where n is the number of approximation point generators. This approximation algorithm is suitable for generating the GVD serving as a base for sampling-based robot motion planning methods, especially for robots with many degrees of freedom, by assuring the maximal clearance distance from surrounding obstacles.

Druh

D - Stať ve sborníku

CEP obor

JC - Počítačový hardware a software

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2006

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 12th International Conference on Soft Computing MENDEL 2006

ISBN

80-214-3195-4

ISSN

—

e-ISSN

—

Počet stran výsledku

11

Strana od-do

124-134

Název nakladatele

Brno University of Technology

Místo vydání

Brno

Místo konání akce

Brno University of Technology

Datum konání akce

31. 5. 2006

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

WRD - Celosvětová akce

Kód UT WoS článku

—