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.


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.

Download: [img] Postscript
Download (304kB) | Preview
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Paper (Technical Report)
Citations: No citation data.
Uncontrolled Keywords: computational geometry Delaunay triangulation robust algorithms Voronoi diagram
Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
Related URLs:
Deposit Information:
ZAIK Number: zpr94-158
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