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

Result code in 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>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

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

Original language description

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.

Czech name

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

Czech description

Č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 sezajištěním maximální vzdálenosti od sousedních překážek.

Type

D - Article in proceedings

CEP classification

JC - Computer hardware and software

OECD FORD branch

—

Project

—

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2006

Confidentiality

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

Article name in the collection

Proceedings of the 12th International Conference on Soft Computing MENDEL 2006

ISBN

80-214-3195-4

ISSN

—

e-ISSN

—

Number of pages

11

Pages from-to

124-134

Publisher name

Brno University of Technology

Place of publication

Brno

Event location

Brno University of Technology

Event date

May 31, 2006

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—