CGGC Seminar: Solving Piecewise Polynomial Constraint Systems with Decomposition using Subdivision-Based Solver

בוריס ואן-סוסין (מדעי המחשב, טכניון)
יום ראשון, 5.3.2017, 13:30
חדר 337, בניין טאוב למדעי המחשב

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

בחזרה לאינדקס האירועים