Improving accuracy in a robust algorithm for three-Dimensional voronoi diagrams.

Journal of Graphics Tools, 1(1):33--45, 1996.

This paper descirbes 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.

This paper is available as a compressed Postscript file Hub96b.ps.gz (122K).