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
      Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE