Construction of the Voronoi diagram for 'one million' generators in single-precision arithmetic
Kōkichi Sugihara, Masao Iri · Proceedings of the IEEE · 1992
A numerically stable algorithm for constructing Voronoi diagrams in the plane is presented. In this algorithm higher priority is placed on the topological structure than on numerical values, so that, however large the numerical errors, the algorithm will never come across topological inconsistency and thus can always complete its task. The behavior of the algorithm is shown with examples, including one for as many as 10/sup 6/ generators.>