Splines over Voronoi Diagrams


Contact: Gerald Farin and Dianne Hansford


Collaborators: Tom Bobach and Georg Umlauf, Univ. of Kaiserslautern, Germany


Funding: NSF grant 0306385 “Splines over Iterated Voronoi Diagrams” and DFG grant 1131 on “Visualization of Large Unstructured Data – Applications in Geospatial Planning, Modeling and Engineering”


Project Details:


A Voronoi diagram is a fundamental geometric structure for dealing with 2D point sets. See next figure for an example. (Voronoi diagram: red, point set: yellow)

Various aspects of splines over Voronoi diagrams were discovered and pursued. One is an application of Sibson splines to the solution of Laplace’s equation. This was discovered by G. Farin, T. Bobach, D. Hansford, and G. Umlauf. Since Sibson’s interpolant is based on a geometric identity among points in the plane, it allows for an iterative scheme for solving Laplace’s equation which is superior to schemes which are based on triangular interpolants.

Another aspect of Sibson splines is that they are not naturally defined outside the convex hull of the data points. Work by D. Hansford, G. Farin, and T. Bobach has shown how to extrapolate Sibson splines. See following figure.

Voronoi diagram

Finally, the use of splines is currently focusing more on approximation than on interpolation. We have (ongoing work by G. Farin, D. Hansford, W. Chen) generalized Sibsonís interpolation scheme to a least squares approximation scheme for scattered data. See next figure.

Voronoi diagram