Accession Number : ADA318637
Title : Low Degree Algorithms for Computing and Checking Gabriel Graphs. (Extended Abstract).
Descriptive Note : Technical rept.,
Corporate Author : BROWN UNIV PROVIDENCE RI
Personal Author(s) : Liotta, Giuseppe
PDF Url : ADA318637
Report Date : 1996
Pagination or Media Count : 13
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 optimal degree procedure is proposed.
Descriptors : *ALGORITHMS, *GRAPHS, OPTIMIZATION, COMPUTATIONS, LINEAR PROGRAMMING, POLYNOMIALS, ARITHMETIC, PLANE GEOMETRY.
Subject Categories : Numerical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE