TY - GEN

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

AU - Bartoň, Michael

AU - Elber, Gershon

AU - Hanniel, Iddo

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

KW - Kinematic synthesis

KW - Trisector curves

KW - Underconstrained polynomial systems

KW - Univariate solution spaces

UR - http://www.scopus.com/inward/record.url?scp=77958028974&partnerID=8YFLogxK

U2 - 10.1145/1839778.1839811

DO - 10.1145/1839778.1839811

M3 - Conference contribution

AN - SCOPUS:77958028974

SN - 9781605589848

T3 - Proceedings - 14th ACM Symposium on Solid and Physical Modeling, SPM'10

SP - 207

EP - 212

BT - Proceedings - 14th ACM Symposium on Solid and Physical Modeling, SPM'10

T2 - 14th ACM Symposium on Solid and Physical Modeling, SPM'10

Y2 - 1 September 2010 through 3 September 2010

ER -