Time complexity of practical parallel steiner point insertion algorithms
Daniel A. Spielman, Shang‐Hua Teng, Alper Üngör · 2004
An effective method in practice to compute quality Delaunay triangulations is to apply parallel refinements that insert Steiner points whose prestars in the triangulation do not overlap. We show that these algorithms can be implemented in O(logm) time using m processors, where m is the output size. To our knowledge, this is the first such analysis. Categories and Subject Descriptors F.2.2 [Nonnumerical Algorithms and Problems]: Geo-metrical problems and computations; G.2.m [Discrete Math-