Worst Case Complexity of Parallel Triangular Mesh Refinement by Longest Edge Bisection.

Abstract

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1996
Accession Number
ADA322954

Entities

People

  • Can Oezturan

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Conformity
  • Data Sets
  • Differential Equations
  • Engineering
  • Information Operations
  • Language
  • Lists (Data Structures)
  • Mathematics
  • Parallel Computing
  • Parallel Processing
  • Partial Differential Equations
  • Template Patterns
  • Three Dimensional
  • Triangles
  • Two Dimensional

Fields of Study

  • Computer science

Readers

  • Computational Fluid Dynamics (CFD)
  • Electromagnetic Wave Scattering and Antenna Radiation Engineering
  • Operations Research