The Taub Faculty of Computer Science Events and Talks

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.