Worst Case Complexity of Parallel Triangular Mesh Refinement by Longest EdgeBisection

摘要

We present a logarithmic algorithm for performing parallel refinement oftriangular meshes by the widely used longest edge bisection procedure. We show that the refinement propagation forms a data dependency which can be expressed as a forest of directed trees. We solve a parallel Euler Tour problem on the trees to propagate the refinement. After propagation, we apply refinement templates. Our algorithm improves earlier reported results which had linear worst case complexity.