A new method of evaluating compact geometric bounds for use in subdivision algorithms (Q1183527)

A major problem in computer graphics methods depending on search or bisection is the construction of a box containing a curve or surface. The authors describe a new method giving smaller boxes than most other methods, based on the following estimate for an \(n\)-th degree polynomial \(f(u)\) on \([0,1]\) evaluated at points \(u_ i\): \[ (n+1)^{-1/2}[\sum^ n_{i=0}f^ 2(u_ i)]^{1/2}\leq \max_{0\leq u\leq 1}| f(u)| \leq C[\sum^ n_{i=0}f^ 2(u_ i)]^{1/2} \] where \(C\) is a function of the \(u_ i\) alone, evaluated on the coefficients of the Lagrange interpolation formula. A proper choice of the \(u_ i\) will give a minimum of \(C\) (determined in the paper for \(n\leq 9\)). The estimate can then be extended to multivariate polynomials and splines and applied to the maximal distance from lines and planes and therefore to the construction of boxes and subdivision algorithms.