Computing Publications

Publications Home » Computing Delaunay triangulation ...

Computing Delaunay triangulation with imprecise input data

Ali Khanban, Abbas Edalat

Conference or Workshop Paper
5th Canadian Conference on Computational Geometry (CCCG'03)

The key step in the construction of the Delaunay triangulation of a finite set of planar points is to establish correctly whether a given point of this set is inside or outside the circle determined by any other three points. We address the problem of formulating the in-circle test when the coordinates of the planar points are given only up to a given precision, which is usually the case in practice. By modelling imprecise points as rectangles, and using the idea of partial disc, we construct a reliable in-circle test that provides the best possible Delaunay triangulation with the imprecise input data given by rectangles.

PDF of full publication (148 kilobytes)
(need help viewing PDF files?)
GZipped Postscript of full publication (163 kilobytes)
(need help viewing GZipped Postscript files?)
BibTEX file for the publication
Conditions for downloading publications from this site. built & maintained by Ashok Argent-Katwala.