A Simple Method for Avoiding Numerical Errors and Degeneracy in Voronoi Diagram Construction

Kokichi SUGIHARA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E75-A   No.4   pp.468-477
Publication Date: 1992/04/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Issue on Discrete Mathematics and Its Application)
Category: 
Keyword: 
Voronoi diagram,  robust algorithm,  degeneracy avoidance,  symbolic perturbation,  

Full Text: PDF>>
Buy this Article



Summary: 
This paper presents a simple method for avoiding both numerical errors and degeneracy in an incremental-type algorithm for constructing the Voronoi diagram with respect to points on a plane. It is assumed that the coordinates of the given points are represented with a certain fixed number of bits. All the computations in the algorithm are carried out in four times higher precision, so that degeneracy can be discerned precisely. Every time degeneracy is found, the points are perturbed symbolically according to a very simple rule and thus are reduced to a nondegenerate case. The present technique makes a computer program simple in the sense that it avoids all numerical errors and requires no exceptional branches of processing for degenerate cases.