Algorithme Dependant de la Sortie pour la Triangulation de Delaunay 3Dd'Ensembles de Points Constraints (Output Sensitive Construction of the 3D Delaunay Triangulation of Constrained Sets of Points)

摘要

Two algorithms to compute the Delaunay triangulation of a set S of n points inthree dimensional (3D) space when the points lie on a set P of k planes are presented. If k = 2, the algorithm runs in time O(n log n + t) where t is the size of the output; if k is greater than or equal to 3, the time bound is O(tk log n). In both cases, the storage is O(n).