OUTPUT SENSITIVE CONSTRUCTION OF THE DELAUNAY TRIANGULATION OF POINTS LYING IN TWO PLANES
Jean‐Daniel Boissonnat, André Cérézo, Olivier Devillers, Monique Teillaud · International Journal of Computational Geometry & Applications · 1996
In this paper, we propose an algorithm to compute the Delaunay triangulation of a set [Formula: see text] 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).