Tech Report CS-96-28

Low Degree Algorithms for Computing and Checking Gabriel Graphs

Giuseppe Liotta

October 1996


In the context of robust computational geometry we focus on the problem of computing and checking Gabriel graphs with algorithms that are not affected by degenaracies and have low arithmetic demand. A simple and practical linear-time algorithm is presented that constructs the Gabriel Graph of a finite point set on the plane from its Delaunay diagram. The degree of the algorithm, i.e.\ a measure of the arithmetic precision required to carry out exact computations, is evaluated and proved to be optimal. The problem of certifying the correctness of an algorithm that computes the Gabriel graph is also investigated and an otpimal degree procedure is proposed.

(complete text in pdf or gzipped postscript)