Detail publikace
Konstrukce 2D zobecněného Voroného diagramu, část I: Aproximační algoritmus
ŠVEC, P.
Český název
Konstrukce 2D zobecněného Voroného diagramu, část I: Aproximační algoritmus
Anglický název
A Construction of the 2D Generalized Voronoi Diagram, Part I: An Approximation Algorithm
Typ
článek ve sborníku ve WoS nebo Scopus
Jazyk
en
Originální abstrakt
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.
Český abstrakt
Článek předkládá nový aproximační algoritmus pro výpočet zobecněného Vorového diagramu (GVD) pro bodové, liniové nebo polygonové generátory, založený na Fortuneho zametacím algoritmu. Algoritmus aproximuje liniový generátor nebo polygonový hranový generátor sekvencí bodových generátorů s danou přesností. Přístup se snaží o detekci hran v úzkých koridorech, které jsou aproximovány větším množstvím bodů, a tím výpočet je rychlejší než v případě uniformní distribuce se stejnou přesností v těchto koridorech. Časová složitost výpočtu se rovná O(n log n), kde n se rovná počtu aproximačních bodových generátorů. Aproximační algoritmus je vhodný pro generování GVD sloužící jako základ vzorkovacích (sampling-based) metod pro roboty s vysokým stupněm volnosti se zajištěním maximální vzdálenosti od sousedních překážek.
Anglický abstrakt
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.
Klíčová slova česky
zobecněný Voroného diagram, Fortuneho zametací algoritmus
Klíčová slova anglicky
Generalized Voronoi diagram, Fortune’s plane sweep algorithm
Rok RIV
2006
Vydáno
01.05.2006
Nakladatel
Brno University of Technology
Místo
Brno
ISBN
80-214-3195-4
Kniha
Proceedings of the 12th International Conference on Soft Computing MENDEL 2006
Ročník
2006
Počet stran
11
BIBTEX
@inproceedings{BUT24983,
author="Petr {Švec},
title="A Construction of the 2D Generalized Voronoi Diagram, Part I: An Approximation Algorithm",
booktitle="Proceedings of the 12th International Conference on Soft Computing MENDEL 2006",
year="2006",
volume="2006",
month="May",
publisher="Brno University of Technology",
address="Brno",
isbn="80-214-3195-4"
}