Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, May, 1995, Las Vegas, NV.

134k compressed postscript of paper

**Abstract:**
We present new geometrical and numerical analysis structure theorems
for the Delaunay diagram of point sets in R^d for a fixed d where
the point sets arise naturally in numerical methods. In particular,
we show that if the largest ratio of the circum-radius to the length
of smallest edge over all simplexes in the Delaunay diagram of P,
DT(P), is bounded, (called the bounded radius-edge ratio property),
then DT(P) is a subgraph of a density graph, the Delaunay spheres
form a k-ply system for a constant k, and that we get optimal
rates of convergence for approximate solutions of Poisson's equation
constructed using control volume techniques. The density graph result
implies that DT(P) has a partition of cost O(n^{1-1/d}) that can
be efficiently found by the geometric separator algorithm of Miller,
Teng, Thurston, and Vavasis and therefore
the numerical linear system defined on
DT(P) using the finite-volume method can be solved efficiently on a
parallel machine (either by a direct or an iterative method). The
constant ply structure of Delaunay spheres leads to a linear-space
point location structure for these Delaunay diagrams with O(log n)
time per query. Moreover, we present a new parallel algorithm for
computing the Delaunay diagram for these point sets in any fixed
dimension in O(log n) random parallel time and $n$ processors. Our
results show that the bounded radius-edge ratio property is desirable
for well-shaped triangular meshes for numerical methods such as finite
element, finite difference, and in particular, finite volume methods.

@inproceedings{MiTaTeWa95, Author="G.~L. Miller and D. Talmor and S.~H. Teng and N.~Walkington", Title="A Delaunay Based Numerical Method for Three Dimensions: Generation, Formulation, and Partition", Booktitle="Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing", Year=1995, month=May}