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

Michael Bartoň*, Gershon Elber, Iddo Hanniel

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations

Abstract

We present an algorithm which robustly computes the intersection curve(s) of an under-constrained piecewise polynomial system consisting of n equations with n+1 unknowns. The solution of such a system is typically a curve in ℝn+1. This work extends the single solution test of [6] for a set of algebraic constraints from zero dimensional solutions to univariate solutions, in ℝn+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 application of the solver, like 3D trisector curves or kinematic simulations in 3D are discussed.

Original languageEnglish (US)
Title of host publicationProceedings - 14th ACM Symposium on Solid and Physical Modeling, SPM'10
Pages207-212
Number of pages6
DOIs
StatePublished - 2010
Externally publishedYes
Event14th ACM Symposium on Solid and Physical Modeling, SPM'10 - Haifa, Israel
Duration: Sep 1 2010Sep 3 2010

Other

Other14th ACM Symposium on Solid and Physical Modeling, SPM'10
CountryIsrael
CityHaifa
Period09/1/1009/3/10

Keywords

  • Kinematic synthesis
  • Trisector curves
  • Underconstrained polynomial systems
  • Univariate solution spaces

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design
  • Algebra and Number Theory
  • Geometry and Topology

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