  The maximum volume principle is investigated as a means to solve the
following problem: Given a set of arbitrary interpolation nodes, how to choose
a set of polynomial basis functions for which the Lagrange interpolation
problem is well-defined with reasonable interpolation error? The interpolation
error is controlled by the Lebesgue constant of multivariate polynomial
interpolation and it is proven that the Lebesgue constant can effectively be
bounded by the reciprocals of the volume (i.e., determinant in modulus) and the
minimal singular value of the multidimensional Vandermonde matrix associated
with the interpolation problem. This suggests that a large volume of the
Vandermonde system can be used as an indicator of accuracy and stability of the
resulting interpolating polynomial. Numerical examples demonstrate that the
approach outlined in this paper works remarkably well in practical
computations.
