Construction of Voronoi Diagram using the Hollow Sphere Concept

This paper implements an algorithm for constructing Voronoi regions using the method we call "hollow sphere". This principle uses the circle, sphere or hyper-sphere as a geometric structure taking into account an Euclidean space of an arbitrary dimension. Boris Deloné used the property of the empty circle to build the Delaunay triangulation; in our case, the same property is used to perform the validations of the hollow spheres, but without using triangles as a fundamental structure. For convenience sake, the hollow sphere as a circle so as to work in two dimensions will be explained and illustrated. However, there is no impediment to working with spheres to take the principles to a three-dimensional space. Furthermore, the properties of the hollow sphere are detailed and an algorithm of incremental construction is used with O(nlogn) time.