[BANANA] Berkeley Lab - Scientific Computing Seminar, Tuesday, April 24, 2007

[Esmond G. Ng]

Berkeley Lab Scientific Computing Seminar

Date:  Tuesday, April 24, 2007
Time:  1:00pm-2:00pm
Location:  Building 70-191

Seminar Speaker:
    Gary L Miller
    Computer Science Department
    Carnegie Mellon University

Title:  Meshing in Fixed Dimension in near Optimal Work and Time

Abstract:
    A new meshing algorithm will be presented for meshing with
boundaries in any fixed dimension, Sparse Voronoi Refinement (SVR). The
meshing problem in 3D, for example, takes as input a a domain and a
collection of features(points, edges, and faces) and decomposes the
domain into tetrahedra.

There are four important properties that a meshing algorithm should have:
1) The tetrahedra should have good aspect ratio, no small angles.
2) The mesh should conform to the features.
3) The size should be competitive to an optimal-size mesh.
4) The algorithm should be work and time competitive with a optimal
algorithm.

SVR is the first algorithm known to have have all four properties even
in 3D for a reasonable assumption about the input.

Over the last 17 years computer scientists have been in the forefront in
designing algorithms with guarantees for all four conditions, beginning
with the pioneering work of Bern, Eppstein, and Gilbert on quadtree
meshing in 1990. Their algorithm has all 4 guarantees for 2D points
where the work is O(n log L/s + m). Here L/s is the ratio of the size of
the domain over the smallest input feature. In 1993 Ruppert proposed a
method called Delaunay Refinement which included guarantees for the
first three conditions in 2D.

The 3D octtree algorithms starts by insuring 1) always and finishes by
insuring 2), while Delaunay Refinement algorithms first insure 2) then
refine until 1) is satisfied. SVR can be viewed as a compromise by
alternately insuring 1) and then 2). SVR has sequential-time/work bounds
of O(n log L/s + m) for inputs in any fixed dimension with
piecewise-linear constraining (PLC) features. The parallel time is O(log
L/s log m) on an EREW PRAM, with the same work. SVR is straightforward
enough that it is likely to be extremely fast in practice.

This represents joint work with Benoit Hudson and Todd Phillips