MINVO Basis: Finding Simplexes with Minimum Volume Enclosing Polynomial Curves. (October 2022)

• Record Type: Journal Article
• Authors: Tordesillas, Jesus; How, Jonathan P.
• Is Part Of: Computer aided design. Volume 151(2022)
• Publication Date: 2022-10
• Subjects: Minimum enclosing simplex -- Curve with largest convex hull -- Polynomial basis -- Polynomial curve -- Spline; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2022.103341
• Languages: English
• ISSNs: 0010-4485

Abstract

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 .