Computing Voronoi Diagram of Higher Order Geometric Objects

Voronoi diagrams, named after the Russian mathematician Georgy Feodosievych Voronoy, are geometric structures that have been extensively studied in Computational Geometry. A Voronoi diagram can be constructed for a set of geometric objects called sites. The geometric objects can be points, lines, circles, curves, surfaces, spheres, etc. A Voronoi diagram divides the space into regions called Voronoi cells such that there is a Voronoi cell corresponding to each object in the input set. A Voronoi cell is a set of points closer to the corresponding object than any other object in the input set.

Applications of the Voronoi diagram can be seen in various ¿elds of science and engineering. Voronoi diagram is used in the motion planning and collision avoidance for robotic motion. Candeloro used the Voronoi diagram of a point set in a 3D space to develop a path-planning system for Unmanned Underwater Vehicles (UUVs). In town planning, the Voronoi diagram can be used for the e¿cient allocation of resources. Image segmentation and feature extraction are other areas where properties of the Voronoi diagram are utilized. similar applications can be seen in disease research and diagnosis.

Voronoi diagram of a set of circles is used for sensor deployment where the radius of a circle represents the range of a sensor. It is also used in cable packing of electric wires to ¿nd the enclosing circle with a minimum radius.