IKCEST

Journal of Computational Geometry | Vol.2, Issue.1 | 2017-05-30 | Pages

Delaunay triangulation of imprecise points, preprocess and actually get a fast query time

Olivier Devillers

Abstract

We propose a new algorithm to preprocess a set of n disjoint unit disks in O(n log n) expected time, allowing to compute the Delaunay triangulation of a set of n points, one from each disk, in O(n) expected time. Our algorithm has the same asymptotic complexity as previous ones for this problem, but our algorithm is much simpler and it runs faster in practice than a direct computation of the Delaunay triangulation.

Original Text (This is the original text for your reference.)

Delaunay triangulation of imprecise points, preprocess and actually get a fast query time

+More

Keywords

unit disks expected the delaunay triangulation asymptotic complexity

Cite this article

APA

MLA

Chicago

Olivier Devillers,.Delaunay triangulation of imprecise points, preprocess and actually get a fast query time. 2 (1),.

References

Disclaimer: The translated content is provided by third-party translation service providers, and IKCEST shall not assume any responsibility for the accuracy and legality of the content.