This paper surveys two methods for designing numerically robust geometric algorithms. The first method is the exact-arithmetic method, in which numerical computations are done in sufficiently high precision so that all the topological judgements can be done correctly. This method is usually accompanied with lazy evaluation and symbolic perturbation in order to reduce the computational cost and the implementation cost. The second method is the topology-oriented method, in which the consistency of the topological structure is considered as higher-priority information than numerical computation, and thus inconsistency is avoided. Both of the methods are described with the implementation examples.

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.