Topologically guaranteed bivariate solutions of under-constrained multivariate piecewise polynomial systems. (January 2015)

• Record Type: Journal Article
• Authors: Mizrahi, Jonathan; Elber, Gershon
• Is Part Of: Computer aided design. Volume 58(2015)
• Page Start: 210
• Page End: 219
• Publication Date: 2015-01
• Subjects: Subdivision solvers -- Polynomial equations -- Implicit surfaces -- B-spline basis functions; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2014.08.026
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: We present a subdivision based algorithm to compute the solution of an under-constrained piecewise polynomial system of n − 2 equations with n unknowns, exploiting properties of B-spline basis functions. The solution of such systems is, typically, a two-manifold in R n . To guarantee the topology of the approximated solution in each sub-domain, we provide subdivision termination criteria, based on the (known) topology of the univariate solution on the domain's boundary, and the existence of a one-to-one projection of the unknown solution on a two dimensional plane, in R n . We assume the equation solving problem is regular, while sub-domains containing points that violate the regularity assumption are detected, bounded, and returned as singular locations of small (subdivision tolerance) size. This work extends (and makes extensive use of) topological guarantee results for systems with zero and one dimensional solution sets. Test results in R 3 and R 4 are also demonstrated, using error-bounded piecewise linear approximations of the two-manifolds. Highlights: A subdivision algorithm for 2-DOF nonlinear algebraic systems. Topologically guaranteed subdivision termination criteria in R n, n ≥ 3 . A tessellation method for two-manifolds in R n .