On the Optimality of Piecewise Linear Max-norm Enclosures based on Slefes
Jörg Peters, Xiaobin Wu · 2002
Abstract. Subdividable linear efficient function enclosures (Slefes) provide, at low cost, a piecewise linear pair of upper and lower bounds f +, f − , that sandwich a function f on a given interval: f + ≥ f ≥ f −. In practice, these bounds are observed to be very tight. This paper addresses the question just how close to optimal, in the max-norm, the slefe construction actually is. Specifically, we compare the width f + −f − of the slefe to the narrowest possible piecewise linear enclosure of f when f is a univariate cubic polynomial. Due to curved geometry, objects in b-spline, Bézier or generalized subdivision representation pose numerical and implementation challenges when measuring distance between objects, re-approximating for format conversion, meshing with tolerance, or detecting the silhouette. Naive linearization,