The Delaunay Triangulation and Function Learning

TitleThe Delaunay Triangulation and Function Learning
Publication TypeTechnical Report
Year of Publication1990
AuthorsOmohundro, S.
Other Numbers565

In this report we consider the use of the Delaunay triangulation for learning smooth nonlinear functions with bounded second derivatives from sets of random input output pairs. We show that if interpolation is implemented by piecewise-linear approximation over a triangulation of the input samples, then the Delaunay triangulation has a smaller worst case error at each point than any other triangulation. The argument is based on a nice connection between the Delaunay criterion and quadratic error functions. The argument also allows us to give bounds on the average number of samples needed for a given level of approximation.

Bibliographic Notes

ICSI Technical Report TR-90-001

Abbreviated Authors

S. M. Omohundro

ICSI Publication Type

Technical Report