A Practical Method for Computing Correct Delaunay Triangulations in the Euclidian Metric

Jünger, Michael, Kaibel, Volker and Thienel, Stefan (1994). A Practical Method for Computing Correct Delaunay Triangulations in the Euclidian Metric. ["eprint_fieldopt_monograph_type_preprint" not defined].

Full text not available from this repository.

Abstract

The correctness of many algorithms for computing Delaunay triangulations for the Euclidean Metric (as well as for several other problems in Computational Geometry) basically depends on the correct evaluation of the signs of certain arithmetical expressions with integer operands. Since the numbers to deal with often exceed the bounds up to which computers are able to calculate exactly, one has to employ expensive software arithmetic (''big integer packets'') to provide correctness in many cases. We present a method to decide dynamically (i.e., for each evaluation occurring during a run of the used algorithm) if it is necessary to perform it by software arithmetic or if one can guarantee the correct evaluation when using a certain 'ìnexact'' hardware arithmetic, e.g., the floating point arithmetic of the used system. We apply this method to the computation of Delaunay triangulations and report about some computational results.

Item Type:

Preprints, Working Papers or Reports (["eprint_fieldopt_monograph_type_preprint" not defined])

Creators: