Output-sensitive construction of the Delaunay triangulation of points lying in two planes

Abstract : 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).
Type de document :
Article dans une revue
International Journal of Computational Geometry and Applications, World Scientific Publishing, 1996, 6 (1), pp.1-14. 〈10.1142/S0218195996000022〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00795075
Contributeur : Olivier Devillers <>
Soumis le : mercredi 27 février 2013 - 11:22:42
Dernière modification le : samedi 27 janvier 2018 - 01:31:46

Lien texte intégral

Identifiants

Collections

Citation

Jean-Daniel Boissonnat, André Cerezo, Olivier Devillers, Monique Teillaud. Output-sensitive construction of the Delaunay triangulation of points lying in two planes. International Journal of Computational Geometry and Applications, World Scientific Publishing, 1996, 6 (1), pp.1-14. 〈10.1142/S0218195996000022〉. 〈hal-00795075〉

Partager

Métriques

Consultations de la notice

209