Solving polynomial systems using no-root elimination blending schemes

Michael Barton

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

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
Volume43
Issue number12
DOIs
StatePublished - Dec 2011

ASJC Scopus subject areas

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

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

Cite this