MINVO Basis: Finding Simplexes with Minimum Volume Enclosing Polynomial Curves. (October 2022) - Tordesillas, Jesus; How, Jonathan P.
Abstract: This paper studies the polynomial basis that generates the smallest n -simplex enclosing a given n th -degree polynomial curve in R n . Although the Bernstein and B-Spline polynomial bases provide feasible solutions to this problem, the simplexes obtained by these bases are not the smallest possible, which leads to overly conservative results in many CAD (computer-aided design) applications. We first prove that the polynomial basis that solves this problem (MINVO basis) also solves for the n th -degree polynomial curve with largest convex hull enclosed in a given n -simplex. Then, we present a formulation that is independent of the n -simplex or n th -degree polynomial curve given. By using Sum-Of-Squares (SOS) programming, branch and bound, and moment relaxations, we obtain high-quality feasible solutions for any n ∈ N, and prove (numerical) global optimality for n = 1, 2, 3 and (numerical) local optimality for n = 4 . The results obtained for n = 3 show that, for any given 3 rd -degree polynomial curve in R 3, the MINVO basis is able to obtain an enclosing simplex whose volume is 2.36 and 254.9 times smaller than the ones obtained by the Bernstein and B-Spline bases, respectively. When n = 7, these ratios increase to 902.7 and 2 . 997 ⋅ 1 0 21, respectively. Highlights: The MINVO basis finds the smallest n -simplex enclosing a polynomial curve. The MINVO basis finds the polynomial curve with largest convex hull in an n -simplex. Improvements up to several orders of magnitude with respect to Bernstein/B-Spline. Numerical global optimality is proven for n = 1, 2, 3. High-quality feasible solutions are obtained for any degree n .