Output-sensitive construction of the Delaunay triangulation of points lying in two planes
Résumé
In this paper, we propose an algorithm to compute the Delaunay triangulation of a set of n points in 3-dimensional space when the points lie in 2 planes. The algorithm is output-sensitive and optimal with respect to the input and the output sizes. Its time complexity is O(n log n+t), where t is the size of the output, and the extra storage is O(n).
Origine : Fichiers produits par l'(les) auteur(s)
Loading...