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

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 surface-surface intersection problem, computing 3D trisector curves, flecnodal curves or kinematic simulations in 3D are also discussed. (C) 2011 Elsevier Ltd. All rights reserved.