Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

CGGC Seminar: Solving Piecewise Polynomial Constraint Systems with Decomposition using Subdivision-Based Solver
event speaker icon
Boris van Sosin (CS, Technion)
event date icon
Sunday, 21.05.2017, 13:30
event location icon
Taub 401
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.