In the knowledge transfer from computational geometry to applications in graphics and manufacturing, there is a strong need for reliable implementations of geometric algorithms. This need has prompted intensive and successful research into robust computational geometry. The paper contributes to one stream of this research, which assumes exact computations for error-free data points given as b-bit integers. The authors introduce the concept of the degree of the algorithm (the number of bits needed to perform exact computations for the algorithm) together with an efficient method to evaluate this degree. The concept is equivalent to Burnikel’s notion of the precision of an algorithm and is related to Yap’s concept of the degree of derivation. The authors argue that the degree is as important to the efficiency of geometric algorithms as is the asymptotic time complexity. This type of analysis is illustrated on a number of algorithms for proximity problems that can be solved with Voronoi diagrams. The quality of the algorithms is measured by the degree and the running time. The results, together with insightful discussion of issues in robust implementations of geometric algorithms, are of interest both to computational geometers and to practitioners.