Construcción de Diagramas de Voronoi empleando el Concepto de la Esfera Hueca (Construction of Voronoi Diagram using the Hollow Sphere Concept)

Netz Romero (, Ricardo Barrón (

1Instituto Politécnico Nacional

This paper appears in: Revista IEEE América Latina

Publication Date: May 2017
Volume: 15,   Issue: 5 
ISSN: 1548-0992

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.

Index Terms:
Voronoi diagrams, Delaunay triangulations, hollow sphere.   

Documents that cite this document
This function is not implemented yet.

[PDF Full-Text (855)]