MINVO Basis: Finding Simplexes with Minimum Volume Enclosing Polynomial
Curves
J. Tordesillas, и J. How. (2020)cite arxiv:2010.10726Comment: 17 pages, 16 figures.
Аннотация
Outer polyhedral representations of a given polynomial curve are extensively
exploited in computer graphics rendering, computer gaming, path planning for
robots, and finite element simulations. Bézier curves (which use the
Bernstein basis) or B-Splines are a very common choice for these polyhedral
representations because their non-negativity and partition-of-unity properties
guarantee that each interval of the curve is contained inside the convex hull
of its control points. However, the convex hull provided by these bases is not
the one with smallest volume, producing therefore undesirable levels of
conservatism in all of the applications mentioned above. This paper presents
the MINVO basis, a polynomial basis that generates the smallest $n$-simplex
that encloses any given $n^th$-order polynomial curve. The results
obtained for $n=3$ show that, for any given $3^rd$-order polynomial
curve, 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\cdot10^21$, respectively.
%0 Generic
%1 tordesillas2020minvo
%A Tordesillas, Jesus
%A How, Jonathan P.
%D 2020
%K 2020 geometry linear-algebra siggraph
%T MINVO Basis: Finding Simplexes with Minimum Volume Enclosing Polynomial
Curves
%U http://arxiv.org/abs/2010.10726
%X Outer polyhedral representations of a given polynomial curve are extensively
exploited in computer graphics rendering, computer gaming, path planning for
robots, and finite element simulations. Bézier curves (which use the
Bernstein basis) or B-Splines are a very common choice for these polyhedral
representations because their non-negativity and partition-of-unity properties
guarantee that each interval of the curve is contained inside the convex hull
of its control points. However, the convex hull provided by these bases is not
the one with smallest volume, producing therefore undesirable levels of
conservatism in all of the applications mentioned above. This paper presents
the MINVO basis, a polynomial basis that generates the smallest $n$-simplex
that encloses any given $n^th$-order polynomial curve. The results
obtained for $n=3$ show that, for any given $3^rd$-order polynomial
curve, 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\cdot10^21$, respectively.
@misc{tordesillas2020minvo,
abstract = {Outer polyhedral representations of a given polynomial curve are extensively
exploited in computer graphics rendering, computer gaming, path planning for
robots, and finite element simulations. B\'ezier curves (which use the
Bernstein basis) or B-Splines are a very common choice for these polyhedral
representations because their non-negativity and partition-of-unity properties
guarantee that each interval of the curve is contained inside the convex hull
of its control points. However, the convex hull provided by these bases is not
the one with smallest volume, producing therefore undesirable levels of
conservatism in all of the applications mentioned above. This paper presents
the MINVO basis, a polynomial basis that generates the smallest $n$-simplex
that encloses any given $n^\text{th}$-order polynomial curve. The results
obtained for $n=3$ show that, for any given $3^{\text{rd}}$-order polynomial
curve, 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\cdot10^{21}$, respectively.},
added-at = {2021-04-03T23:49:27.000+0200},
author = {Tordesillas, Jesus and How, Jonathan P.},
biburl = {https://www.bibsonomy.org/bibtex/2d86901cca7eb86a9a79b2e9f09d0f54c/analyst},
description = {[2010.10726] MINVO Basis: Finding Simplexes with Minimum Volume Enclosing Polynomial Curves},
interhash = {fdce00a045b882902f55372b264164f4},
intrahash = {d86901cca7eb86a9a79b2e9f09d0f54c},
keywords = {2020 geometry linear-algebra siggraph},
note = {cite arxiv:2010.10726Comment: 17 pages, 16 figures},
timestamp = {2021-04-03T23:49:27.000+0200},
title = {MINVO Basis: Finding Simplexes with Minimum Volume Enclosing Polynomial
Curves},
url = {http://arxiv.org/abs/2010.10726},
year = 2020
}