Solving piecewise polynomial constraint systems with decomposition and a subdivision-based solver. (September 2017) - van Sosin, Boris; Elber, Gershon
Abstract: Piecewise polynomial constraint systems are common in numerous problems in computational geometry, such as constraint programming, modeling, and kinematics. We propose a framework that is capable of decomposing, and efficiently solving a wide variety of complex piecewise polynomial constraint systems, that include both zero constraints and inequality constraints, with zero-dimensional or univariate solution spaces. Our framework combines a subdivision-based polynomial solver with a decomposition algorithm in order to handle large and complex systems. We demonstrate the capabilities of our framework on several types of problems and show its performance improvement over a state-of-the-art solver. Graphical abstract: Highlights: A framework for decomposing constraint systems, with a total DoF of zero or one. Combines a univariate solver with a constraint system decomposition algorithm. Functional composition of B-spline multivariates for propagating partial solutions. Capable of globally finding all the solutions to a constraint problem. Demonstrated on problems such as static geometry, kinematics, algebraic problems.