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).
Document type :
Journal articles
Liste complète des métadonnées

https://hal.inria.fr/hal-00795075
Contributor : Olivier Devillers <>
Submitted on : Wednesday, February 27, 2013 - 11:22:42 AM
Last modification on : Saturday, January 27, 2018 - 1:31:46 AM

Identifiers

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⟩

Share

Metrics

Record views

220