Worst Case Complexity of Parallel Triangular Mesh Refinement by Longest Edge Bisection.
Can Özturan · 1997
We present a logarithmic algorithm for performing parallel refinement of triangular 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. This research was supported by the National Aeronautics and Space Administration under NASA Contract No. NAS1-19480 while the author was in residence at the Institute for Computer Applications in Science and Engineering (ICASE), NASA Langley Research Center, Hampton, VA 23681-0001. i 1 1 Introduction Recently, adaptive mesh refinement (AMR) techniques for the solution of partial differential equations have gained importance due to their ability to concentrate computational as well as storage resources to re...