Constructing Approximate Voronoi Diagrams from Digital Images of Generalized Polygons and Circular Objects 

Waldir Roque and Dionísio Doering
Universidade Federal do Rio Grande do Sul
Instituto de Matemática
91509-900 Porto Alegre, RS



Keywords: Voronoi diagrams, Generalized polygons, Digital images.


In this paper we present the geometrical construction of an approximate generalized Voronoi diagram for generalized polygons and circular objects based on their minimum geometrical structure that are extracted from the object's digital image. The construction  is done in  O(n)  time complexity, where n is the number of single points defining the set of objects. An application of this technique has been done for mobile robot path planning.