Name
Abstract | ||
|---|---|---|
The need for robust solutions for sets of non-linear multivariate constraints or equations needs no motivation. Subdivision-based multivariate constraint solvers [1, 2, 3] typically employ the convex hull and subdivision/domain clipping properties of the Bézier/B-spline representation to detect all regions that may contain a feasible solution. Once such a region has been identified, a numerical improvement method is usually applied, which quickly converges to the root. Termination criteria for this subdivision/domain clipping approach are necessary so that, for example, no two roots reside in the same sub-domain (root isolation). This work presents two such termination criteria. The first theoretical criterion identifies sub-domains with at most a single solution. This criterion is based on the analysis of the normal cones of the multiviarates and has been known for some time [1]. Yet, a computationally tractable algorithm to examine this criterion has never been proposed. In this paper, we present such an algorithm for identifying sub-domains with at most a single solution that is based on a dual representation of the normal cones as parallel hyper-planes over the unit hyper-sphere. Further, we also offer a second termination criterion, based on the representation of bounding parallel hyper-plane pairs, to identify and reject sub-domains that contain no solution. We implemented both algorithms in the multivariate solver of the IRIT [4] solid modeling system and present examples using our implementation. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11802914_9 | GMP |
Keywords | Field | DocType |
subdivision termination criterion,robust solution,termination criterion,b-spline representation,normal cone,dual representation,multivariate solver,subdivision-based multivariate constraint solvers,theoretical criterion,single solution,feasible solution,subdivision multivariate solvers,convex hull,solid modeling | B-spline,Constraint satisfaction,Mathematical optimization,Solid geometry,Computer science,Convex hull,Algorithm,Subdivision,Solver,Domain decomposition methods,Convex cone | Conference |
Volume | ISSN | ISBN |
4077 | 0302-9743 | 3-540-36711-X |
Citations | PageRank | References |
6 | 0.65 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Iddo Hanniel | 1 | 197 | 12.98 |
| Gershon Elber | 2 | 1924 | 182.15 |