## Delaunay Triangulations of Imprecise Points in Linear Time after Preprocessing

An assumption of nearly all algorithms in computational geometry is that the input points are given precisely, so it is interesting to ask what is the value of imprecise information about points. We show how to preprocess a set of n disjoint unit disks in the plane in O(n log n) time so that if one point per disk is specified with precise coordinates, the Delaunay triangulation can be computed in linear time. From the Delaunay, one can obtain the Gabriel graph and a Euclidean minimum spanning tree; it is interesting to note the roles that these two structures play in our algorithm to quickly compute the Delaunay.

keywords: Computational Geometry, Data Structures, Delaunay Triangulations, Data Imprecision, UDG

### Journal Article (peer-reviewed)

Jack Snoeyink, Maarten Löffler

Delaunay Triangulations of Imprecise Points in Linear Time after Preprocessing

Computational Geometry: Theory and Applications

43, 3, 234–242, 2010

### Conference Proceedings (peer-reviewed)

Jack Snoeyink, Maarten Löffler

Delaunay Triangulations of Imprecise Points in Linear Time after Preprocessing

Proc. 24th Symposium on Computational Geometry

298–304, 2008

*Invited to Special Issue of CGTA*

back to list