Detail publikace

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

ŠVEC, P.

Originální 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

angličtina

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

Generalized Voronoi diagram, Fortune’s plane sweep algorithm

Autoři

ŠVEC, P.

Rok RIV

2006

Vydáno

1. 5. 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

Strany od

124

Strany do

134

Strany počet

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"
}