Computing Delaunay triangulation with imprecise input data
File(s)
Published version
Author(s)
Khanban, A
Edalat, A
Type
Conference Paper
Abstract
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.
Version
Published version
Date Issued
2003
Citation
2003, pp.94-97
Source Title
15th Canadian Conference on Computational Geometry (CCCG'03)
Start Page
94
End Page
97
Copyright Statement
© The authors
Identifier
http://www.cccg.ca/proceedings/2003/
Source
15th Canadian Conference on Computational Geometry (CCCG'03)
Source Place
Halifax, Nova Scotia, Canada
Start Date
2003-08-11
Finish Date
2003-08-13
Coverage Spatial
Halifax, Nova Scotia, Canada