Topologically guaranteed univariate solutions of underconstrained polynomial systems via no-loop and single-component tests

Michael Barton*, Gershon Elber, Iddo Hanniel

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

27 Scopus citations

Abstract

We present an algorithm which robustly computes the intersection curve(s) of an underconstrained piecewise polynomial system consisting of n equations with n+1 unknowns. The solution of such a system is typically a curve in Rn+1. This work extends the single solution test of Hanniel and Elber (2007) [6] for a set of algebraic constraints from zero-dimensional solutions to univariate solutions, in Rn+1. Our method exploits two tests: a no-loop test (NLT) and a single-component test (SCT) that together isolate and separate domains D where the solution curve consists of just one single component. For such domains, a numerical curve tracing is applied. If one of those tests fails, D is subdivided. Finally, the single components are merged together and, consequently, the topological configuration of the resulting curve is guaranteed. Several possible applications of the solver, namely solving the surfacesurface intersection problem, computing 3D trisector curves, flecnodal curves or kinematic simulations in 3D are also discussed.

Original languageEnglish (US)
Pages (from-to)1035-1044
Number of pages10
JournalCAD Computer Aided Design
Volume43
Issue number8
DOIs
StatePublished - Aug 1 2011

Keywords

  • Flecnodal curve
  • Kinematic synthesis
  • Surfacesurface intersection
  • Trisector curves
  • Underconstrained polynomial systems
  • Univariate solution spaces

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'Topologically guaranteed univariate solutions of underconstrained polynomial systems via no-loop and single-component tests'. Together they form a unique fingerprint.

Cite this