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

Jünger, Michael and Kaibel, Volker and Thienel, Stefan (1994) A Practical Method for Computing Correct Delaunay Triangulations in the Euclidian Metric.
Technical Report , 25 p.

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.


Actions:
Download: [img] Postscript
Download (304kB) | Preview
Export as: [error in script]
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Paper (Technical Report)
Citations: [error in script] [error in script]
Uncontrolled Keywords: [error in script]
Subjects:
Uncontrolled Keywords: computational geometry, Delaunay triangulation, robust algorithms, Voronoi diagram
Subjects: UNSPECIFIED
Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Jan 2012 11:22
Deposit Information:
ZAIK Number: [error in script]
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Jan 2012 11:22
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/158