mit-acl/minvo

Simplexes with Minimum Volume Enclosing Polynomial Curves

MINVO Basis: Finding Simplexes with Minimum Volume Enclosing Polynomial Curves

Example for n=3:

MINVO roots:

Citation

When using MINVO, please cite this paper (pdf, video):

@article{tordesillas2022minvo,
  title={MINVO Basis: Finding Simplexes with Minimum Volume Enclosing Polynomial Curves},
  author={Tordesillas, Jesus and How, Jonathan P},
  journal={Computer-Aided Design},
  volume={151},
  pages={103341},
  year={2022},
  publisher={Elsevier}
}

Instructions to use the MINVO basis

• For a particular curve (Problem 1 of the paper): See an example (with n=3) in curve_given3D.m

• For a particular simplex (Problem 2 of the paper): See an example (with n=3) in simplex_given3D.m

To obtain all the figures of the paper, you can simply run plot_solution.m

You don't need to install any external solvers for the steps above.

Instructions to derive the MINVO basis

• The file general_formulation_sos.m solves Problem 3 in the paper using SOS.
• The file general_formulation_lukacs_theorem.m solves Problem 3 in the paper using the Markov–Lukács Theorem.
• The file formula_formulation.m solves Problem 4 in the paper.

Follow the instructions in each file to prove local/global optimality.

Depending on the settings you choose in each file, you may need to install YALMIP (tested with this release), SNOPT and/or MOSEK.

---

Approval for release: This code was approved for release by The Boeing Company in December 2020.