The Bernstein Basis and its applications in solving geometric constraint systems

Sebti Foufou, Dominique Michelucci

Research output: Contribution to journalArticlepeer-review

Abstract

This article reviews the properties of Tensorial Bernstein Basis (TBB) and its usage, with interval analysis, for solving systems of nonlinear, univariate or multivariate equations resulting from geometric constraints. TBB are routinely used in computerized geometry for geometric modelling in CAD-CAM, or in computer graphics. They provide sharp enclosures of polynomials and their derivatives. They are used to reduce domains while preserving roots of polynomial systems, to prove that domains do not contain roots, and to make existence and uniqueness tests. They are compatible with standard preconditioning methods and fit linear programming techniques. However, current Bernstein-based solvers are limited to small algebraic systems. We present Bernstein polytopes and show how combining them with linear programming allows us to solve larger systems as well. The article also gives a generalization of Bernstein polytopes to higher degrees and a comparison of polytopes-based versus TBB-based polynomial bounds.

Original languageEnglish (US)
Pages (from-to)192-208
Number of pages17
JournalReliable Computing
Volume17
StatePublished - Dec 2012

Keywords

  • Algebraic systems
  • Geometric constraint solving. bernstein polytope
  • Tensorial Bernstein Basis
  • Univariate and multivariate polynomials

ASJC Scopus subject areas

  • Software
  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'The Bernstein Basis and its applications in solving geometric constraint systems'. Together they form a unique fingerprint.

Cite this