Abstract

A Voronoi hierarchy is a new, general form of multiresolution hierarchies. The method can be applied to a variety of data including scattered data, arbitrarily gridded data, and data on multi-dimensional domains.

To create a Voronoi hierarchy, an initial Voronoi diagram must first be created to represent the coarsest level of detail. Second, points are inserted into the existing diagram to create higher levels of resolution. The first level in the hierarchy is defined by the points which form the convex hull of the data set. Successive levels are created by

• identifying a set of cells with high associated error value;
• inserting original data points into these cells;
• updating the Voronoi diagram;
• calculating a global error measure for the updated diagram; and
• repeating these steps until a global error bound is met.

To create an image, a function is assigned to each cell (tile) in the diagram. The images below were generated with a piecewise-constant function, which assigns a data point's associated function to the corresponding cell. Other functions, like the Sibson interpolant, can also be used.

At each iteration of the algorithm, we identify a set of cells with high errors. A cell's error is the sum of errors (considering the L1 norm) for all points in the cell. A point's error is the difference between the point's actual function value and the approximated functional value of the Voronoi cell that contains the point. Inserting a point with maximal error leads to good results. Patterns and discontinuities are detected early by the refinement process.

The original color image is of the Cat's Eye Nebula, and has a resolution of 248x249. The following three images show three resolutions of a Voronoi hierarchy for this image. The first level contains 208 cells and is shown at the left.

This hierarchy contains 737 cells. The second elliptical path in the center is now evident.

The final hierarchy shown has 8284 cells. We now have an excellent representation of the original image at a fraction of the original data size. All elliptical paths now show clearly.

Publications

• Shirley Schussman, Martin Bertram, Bernd Hamann, Kenneth I. Joy, Hierarchical Data Representations based on Planar Voronoi Diagrams, in: Proceedings of the Joint Eurographics and IEEE TVCG Conference on Visualization 2000 (VisSim '00), pp. 63--72, 2000.

Contact