Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
439461 | Computer-Aided Design | 2014 | 9 Pages |
Abstract
Solving polynomial systems of equations is an important problem in many fields such as computer-aided design, manufacturing and robotics. In recent years, subdivision-based solvers, which typically make use of the properties of the Bézier/BB-spline representation, have proven successful in solving such systems of polynomial constraints. A major drawback in using subdivision solvers is their lack of scalability. When the given constraint is represented as a tensor product of its variables, it grows exponentially in size as a function of the number of variables. In this paper, we present a new method for solving systems of polynomial constraints, which scales nicely for systems with a large number of variables and relatively low degree. Such systems appear in many application domains. The method is based on the concept of bounding hyperplane arithmetic, which can be viewed as a generalization of interval arithmetic. We construct bounding hyperplanes, which are then passed to a linear programming solver in order to reduce the root domain. We have implemented our method and present experimental results. The method is compared to previous methods and its advantages are discussed.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Graphics and Computer-Aided Design
Authors
Iddo Hanniel,