Detail publikace
A Construction of the 2D Generalized Voronoi Diagram, Part I: An Approximation Algorithm
ŠVEC, P.
Anglický název
A Construction of the 2D Generalized Voronoi Diagram, Part I: An Approximation Algorithm
Typ
Stať ve sborníku v databázi WoS či 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.
Klíčová slova anglicky
Generalized Voronoi diagram, Fortune’s plane sweep algorithm
Vydáno
2006-05-01
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
Strany od–do
124–
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",
pages="11",
publisher="Brno University of Technology",
address="Brno",
isbn="80-214-3195-4"
}