Astron. Astrophys. 363, L29-L32 (2000)

2. The Delaunay tessellation field estimator

Given a set of field values sampled at a discrete number of locations along one dimension we are familiar with various prescriptions for reconstructing the field over the full spatial domain. The most straightforward way involves the partition of space into bins centered on the sampling points. The field is then assumed to have the - constant - value equal to the one at the sampling point. Evidently, this yields a field with unphysical discontinuities at the boundaries of the bins. A first-order improvement concerns the linear interpolation between the sampling points, leading to a fully continuous field.

In more than one dimension, the equivalent spatial intervals of the 1-D bins are well-known in stochastic geometry. A point process defines a Voronoi tessellation by dividing space into a unique and volume-covering network of mutually disjunct convex polyhedral cells, each of which comprises that part of multidimensional space closer to the defining point than to any of the other (see van de Weygaert 1991and references therein). These Voronoi cells (see Fig. 1) are the multidimensional generalization of the 1-D bins in which the zeroth-order method approximates the field value to be constant. The natural extension to a multidimensional linear interpolation interval then immediately implies the corresponding Delaunay tessellation (Delone 1934). This tessellation (Fig. 1) consists of a volume-covering tiling of space into tetrahedra (in 3-D, triangles in 2-D, etc.) whose vertices are formed by four specific points in the dataset. The four points are uniquely selected such that their circumscribing sphere does not contain any of the other datapoints. The Voronoi and Delaunay tessellation are intimately related, being each others dual in that the centre of each Delaunay tetrahedron's circumsphere is a vertex of the Voronoi cells of each of the four defining points, and conversely each Voronoi cell nucleus a Delaunay vertex (see Fig. 1). The "minimum triangulation" property of the Delaunay tessellation has in fact been well-known and abundantly applied in, amongst others, surface rendering applications such as geographical mapping and various computer imaging algorithms.

Fig. 1. A set of 20 points with their Voronoi (left frame: solid lines) and Delaunay (right frame: solid lines) tesselations. Left frame: the shaded region indicates the Voronoi cell corresponding to the point located just below the center. Right frame: the shaded region is the "contiguous Voronoi cell" of the same point as in the lefthand frame.

Consider a set of N discrete datapoints in a finite region of M-dimensional space. Having at one's disposal the field values at each of the Delaunay vertices , at each location in the interior of a Delaunay M-dimensional tetrahedron the linear interpolation field value is defined by

in which is the estimated constant field gradient within the tetrahedron. Given the field values , the value of the M components of can be computed straightforwardly by evaluating Eq. (1) for each of the M points . This multidimensional procedure of linear interpolation was already described by Bernardeau & van de Weygaert 1996in the context of defining procedures for volume-weighted estimates of cosmic velocity fields. While they explicitly demonstrated that the zeroth-order Voronoi estimator is the asymptotic limit for volume-weighted field reconstructions from discretely sampled field values, they showed the superior performance of the first-order Delaunay estimator in reproducing analytical predictions.

The one factor complicating a trivial and direct implementation of above procedure in the case of density (intensity) field estimates is the fact that the number density of data points itself is the measure of the underlying density field value. Unlike the case of velocity fields, we therefore cannot start with directly available field estimates at each datapoint. Instead, we need to define appropriate estimates from the point set itself. Most suggestive would be to base the estimate of the density field at the location of each point on the inverse of the volume of its Voronoi cell, . Note that in this we take every datapoint to represent an equal amount of mass m. The resulting field estimates are then intended as input for the above Delaunay interpolation procedure. However, one can demonstrate that integration over the resulting density field would yield a different mass than the one represented by the set of sample points (see Schaap & van de Weygaert 2000for a more specific and detailed discussion). Instead, mass conservation is naturally guaranteed when the density estimate is based on the inverse of the volume of the "contiguous" Voronoi cell of each datapoint, . The "contiguous" Voronoi cell of a point is the cell consisting of the agglomerate of all K Delaunay tetrahedra containing point i as one of its vertices, whose volume is the sum of the volumes of each of the K Delaunay tetrahedra. Fig. 1 (righthand panel) depicts an illustration of such a cell. Properly normalizing the mass contained in the reconstructed density field, taking into account the fact that each Delaunay tetrahedron is invoked in the density estimate at locations, we find at each datapoint the following density estimate,

Having computed these density estimates, we subsequently proceed to determine the complete volume-covering density field reconstruction through the linear interpolation procedure outlined in Eq. (1).

© European Southern Observatory (ESO) 2000

Online publication: December 5, 2000
helpdesk.link@springer.de