I have used Voronoi diagrams (and their corresponding Delaunay triangulations) for interpolation routines.