Solving polynomial systems using no-root elimination blending schemes

Michael Barton

Research output: Contribution to journalArticlepeer-review

22 Scopus citations


Searching for the roots of (piecewise) polynomial systems of equations is a crucial problem in computer-aided design (CAD), and an efficient solution is in strong demand. Subdivision solvers are frequently used to achieve this goal; however, the subdivision process is expensive, and a vast number of subdivisions is to be expected, especially for higher-dimensional systems. Two blending schemes that efficiently reveal domains that cannot contribute by any root, and therefore significantly reduce the number of subdivisions, are proposed. Using a simple linear blend of functions of the given polynomial system, a function is sought after to be no-root contributing, with all control points of its BernsteinBézier representation of the same sign. If such a function exists, the domain is purged away from the subdivision process. The applicability is demonstrated on several CAD benchmark problems, namely surfacesurfacesurface intersection (SSSI) and surfacecurve intersection (SCI) problems, computation of the Hausdorff distance of two planar curves, or some kinematic-inspired tasks. © 2011 Elsevier Ltd. All rights reserved.
Original languageEnglish (US)
Pages (from-to)1870-1878
Number of pages9
JournalComputer-Aided Design
Issue number12
StatePublished - Dec 2011

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: This research was partly supported by the New York Metropolitan Research Fund, Technion.

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design
  • Industrial and Manufacturing Engineering
  • Computer Science Applications


Dive into the research topics of 'Solving polynomial systems using no-root elimination blending schemes'. Together they form a unique fingerprint.

Cite this