Cálculo computacional da fronteira do diagrama de Voronoi com dois sítios e um obstáculo circular

Abstract

The Voronoi diagram is a type of decomposition of a given space into subsets in that space. The object of this work is the Voronoi’s diagram when two generating points are located at any positions on the Cartesian plane and there is a circular obstacle. This problem can be applied in the calculation of routes for robots. In case of circular obstacle, in addition to the generating points, it was necessary to create additional points for the calculation of the distance between any point P in the space considered and a generating point in the Diagram of Voronoi. In this dissertation, all point coordinates and all distances were calculated between them exactly. The function of the existing boundary between the cells was also defined. And na algorithm for its construction was presented, as well as numerical examples and figures. The notion of proximity graph was introduced and figures of the proximity graphs of the numerical examples.