## CompSci 269S, Winter 2007: Theory Seminar

### Feb 20, 2007, 2:00pm, in ICS2 144

#
Meshing in Fixed Dimension in near Optimal Work and Time

## Gary Miller, CMU

**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 represent joint work with Benoit Hudson and Todd Phillips