Estimating Interpolation Error: A Combinatorial Approach

Abstract New estimates are established for the error between a function and its linear interpolant over a triangular domain. Results previously established using compactness arguments are established here using combinatorial arguments which provide explicit estimates of the constants. New results include new path embeddings for "convex " graphs and bounds on the Rayleigh quotient of complete bipartite graphs. These results are applicable to anisotropic finite element meshing. 1 Introduction In many areas of Computer Science one approximates a more complicated function with a simpler function. Sometimes the more complicated function is given explicitly such as modeling an object in graphics. For other applications, the function may only be known implicitly, say, as the solution to a partial differential equation