Improving Accuracy in a Robust Algorithm for Three-Dimensional Voronoi Diagrams

This paper describes extensions to a previous algorithm that robustly builds three-dimensional Voronoi diagrams in the presence of inexact numerical computations. The extensions improve the algorithm's accuracy, making its results more nearly represent the proximity properties of an ideal Voronoi diagram. In empirical tests, these extensions have improved accuracy by more than eight orders of magnitude. Complete pseudocode for the algorithm appears in an appendix of this paper.