Boris van Sosin (CS, Technion)
Piecewise polynomial constraint systems are common in numerous problems in computational geometry, such as constraint programming, modeling, and kinematics.
In this talk, we present a framework that is capable of decomposing, and efficiently solving a wide variety of complex piecewise polynomial constraint systems.
The framework we present uses a constraint system decomposition algorithm to break down complex problems into smaller, simpler subproblems. It then solves the subproblems using a subdivision-based polynomial solver, and propages the results from one subproblem to the next using multivariate functional composition.
Our framework supports problems with either zero-dimensional or univariate solution spaces, and also include both zero constraints and inequality constraints.
We will demonstrate the capabilities of our framework on several problems, from simple "point-and-bar" systems through complex kinematic problems to general algebraic problems, and compare its performance to the subdivision-based polynomial solver without decomposition.