A new classification of methods for constructing Voronoi graphs on maps represented by point and polygonal obstacles is proposed. Based on the topology of space, it is proposed to classify the constructed Voronoi graphs as external and internal. Thus, Voronoi graph construction methods can calculate either one of the presented types of Voronoi graphs, or both types. The introduced concepts and the proposed classification will be useful for robotics researchers using the Voronoi graph method when planning the path of mobile robots in various environments.

Keywords: Voronoi graph, classification, Voronoi diagram, weighted graph, topology