Low Degree Algorithms for Computing and Checking Gabriel Graphs. (Extended Abstract).

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1996
Accession Number
ADA318637

Entities

People

  • Giuseppe Liotta

Organizations

  • Brown University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Arithmetic
  • Arithmetic Units
  • Computations
  • Computer Graphics
  • Computer Science
  • Efficiency
  • Errors
  • Geometry
  • Graphics
  • Numbers
  • Pattern Recognition
  • Polygons
  • Precision
  • Recognition
  • Triangles

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Mathematical Modeling and Probability Theory.