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}