Low Degree Algorithms for Computing and Checking Gabriel Graphs
Giuseppe Liotta · 1996
) Giuseppe Liotta Center for Geometric Computing Department of Computer Science, Brown University 115 Waterman Street, Providence, RI 02912--1910, USA [email protected] Abstract 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. Keywords: Computational geometry, robustness, Gabriel graph, Delaunay diagram. Researchsupported in part by the National Science Foundationunder gr...