Certified dimension-aware detection and representation of critical loci of multivariate piecewise polynomial systems

For a piecewise polynomial (e.g. tensor-product B-spline) system $F:D\subset\mathbb{R}^n\to\mathbb{R}^k$ with $k\le n$, the critical solution points — points where $F=\bar{0}$ and the differential $dF$ drops below maximal rank $k$ — are the locations where the solution set may undergo topological change (tangential contact, branching, self-intersection). Mizrahi and Elber (2015) gave a subdivision-based method that detects such points by squaring the over-constrained minors system $G=(F,\text{all }k\times k\text{ minors of }dF)$ into $H=\nabla(\frac{1}{2}\|G\|^2)$, but it stops at detection: it returns sampled point clouds for higher-dimensional critical loci, certifies neither isolation nor the dimension of the critical locus, carries no guarantee that the $H$-reformulation always removes the inherited singularity (examples in which a critical point of $F$ is also a critical point of $H$ can be constructed with a high enough level of degeneracy), and provides no topology-preserving tessellation across singular subdomains. The open problem is to replace this sampled detection with a complete, certified, dimension-aware description of the critical solution set within subdivision-based solving of piecewise polynomial systems.

Background

In solid modeling and computer-aided geometric design (CAGD), many geometric queries reduce to solving $F(\bar{x})=\bar{0}$ where $F:D\subset\mathbb{R}^n\to\mathbb{R}^k$, $k\le n$, is a piecewise polynomial map — most commonly tensor-product B-spline functions, which are polynomials on each cell of a rectangular knot grid and joined across knots with prescribed smoothness. Surface–surface intersection, offsetting, medial-axis computation (loci of points having more than one closest point on the object boundary), and self-intersection detection all produce such systems. The numerically delicate locations are the critical solution points: points $p$ with $F(p)=\bar{0}$ at which the differential matrix $dF_p\in\mathbb{R}^{k\times n}$ has $\mathrm{rank}(dF_p)<k$ (that is, the $k$ rows of $dF_p$ are linearly dependent). At such points the solution set can change topology — tangential contacts, branch points, self-intersections — and standard subdivision solvers, which rely on interval or Bernstein-form coefficient tests to exclude root-free boxes and on Newton-type refinement of transversal (regular) zeros, can miss or mislocate solutions exactly there.

Detecting criticality algebraically means solving, together with $F=\bar{0}$, the simultaneous vanishing of all $k\times k$ minors (sub-determinants) of $dF$ — an over-constrained system of $k+\binom{n}{k}$ equations in $n$ unknowns that itself inherits the rank-deficiency singularity it encodes, so it violates the structural assumptions of subdivision and Newton solvers. Mizrahi and Elber (Computer Aided Geometric Design 40, 2015, DOI 10.1016/j.cagd.2015.10.001) reformulated this as follows: form the over-constrained vector function $G(\bar{x})=(F(\bar{x}),M_{I_1}(\bar{x}),\dots,M_{I_{\binom{n}{k}}}(\bar{x}))$ and the square $n\times n$ system $H(\bar{x})=\nabla(\frac{1}{2}\|G(\bar{x})\|^2)$, i.e. the gradient of half the squared residual. As asserted in [1, Remark 4], the Newton–Raphson iterations on $H$ coincide with the Gauss–Newton least-squares iterations on $G$ (the identity is exact at zeros of $G$, where the second-order term $\sum_i G_i\nabla^2 G_i$ of the Jacobian of $H$ vanishes), so the subdivision solver can isolate and refine zeros of $H$ while using $G$ as additional subdivision-constraints and post-filtering out stationary points of $\|G\|$ that are not zeros of $G$. The method detects isolated critical points that regular solvers miss (e.g. the tangential contact of a monkey saddle — the graph of $z=x^3-3xy^2$, whose central point has three descending valleys — with a paraboloid, or tangency between two rational B-spline surfaces) and, applied to the Steiner surface, returns a dense point cloud along the one-dimensional self-intersection locus.

The companion work of Mizrahi and Elber (Computer-Aided Design 58, 2015, DOI 10.1016/j.cad.2014.08.026) achieved topologically guaranteed solution curves only for the bivariate (one-dimensional solution) case, and the follow-up subdivision framework of van Sosin and Elber (Computer-Aided Design 90, 2017, DOI 10.1016/j.cad.2017.05.023) handles piecewise polynomial constraint systems whose solution spaces are zero-dimensional or univariate — the dimension is prescribed, not certified. In the adjacent field of numerical algebraic geometry (homotopy-continuation study of polynomial solution sets), the analogous questions have machinery — numerical local dimension tests, witness sets (finite samples of generic points that represent positive-dimensional solution components), and interval-arithmetic (Krawczyk-operator) certification of isolated nonsingular zeros of square polynomial systems — but these tools apply to polynomial systems over whole domains and have not been adapted to piecewise polynomial B-spline systems solved by subdivision, nor to critical-set systems that are over-constrained and singular by construction. Recent topology-guaranteed surface/surface intersection algorithms (2022–2023) treat tangential and singular contacts for that specific application, including contacts along curves, but do not provide a general certified treatment of critical loci, and their own evaluations report that commercial geometry kernels still fail on near-critical configurations.

Problem Statement

Given a piecewise polynomial system $F:D\subset\mathbb{R}^n\to\mathbb{R}^k$ with $k\le n$, at least $C^1$ smooth and given in tensor-product B-spline form on the axis-parallel compact box $D=[a_1,b_1]\times\cdots\times[a_n,b_n]$, with numeric tolerance $\varepsilon$ (discontinuities of the input representation at the B-spline knots, if any, being handled as usual by first decomposing the problem into a small set of smoothly represented subproblems, each of which may still admit singular solutions), provide a complete, dimension-aware treatment of its critical solution set

$$C=\{\bar{x}\in D:\ F(\bar{x})=\bar{0},\ \mathrm{rank}(dF_{\bar{x}})<k\},$$

consisting of the following jointly pursued results:

(i) locate all critical points of $F$ in $D$, so that the domain is subdivided into sub-domains containing the critical locations and sub-problems that are strictly regular — admitting no critical points, not even at their boundaries;

(ii) for each critical location, and in particular in the degenerate situation in which a critical point $p$ of $F$ is also a critical point of the minimal-norm reformulation $H=\nabla(\frac{1}{2}\|G\|^2)$ with $G=(F,M_{I_1},\dots,M_{I_{\binom{n}{k}}})$, so that regularity-based isolation does not apply, determine whether it is isolated in $C$ or belongs to a positive-dimensional critical variety, and determine the dimension of that variety — the dimension of the variety of real solutions in the non-regular case, noting that $\mathrm{rank}(dH_p)=n$ is a sufficient but not necessary condition for isolation;

(iii) replace the dense point-cloud approximation of positive-dimensional critical loci by an actual parametric, analytic, or otherwise certified description of the locus; and

(iv) when $k<n$, produce a correct tessellation of the solution manifold (in general dimension) at the singular sub-domains, whose solution yields topologically correct stitching of the regular areas.

These four results are logically linked, and none of them is independently sufficient: (iii) already determines the dimension of a positive-dimensional locus, but it does not settle the isolated (zero-dimensional) case in (ii), nor does it imply the general-dimension tessellation in (iv).

Certification and topological correctness are understood in the source's own terms: subdivision termination and root-isolation criteria at tolerance $\varepsilon$, and topological correctness in the isotopic-meshing / polygonization sense of the literature cited by [1] (e.g. Bloomenthal and Ferguson 1995; Burr et al. 2008; Hass et al. 2007; Stander and Hart 2005). The minimal-norm reformulation $H=\nabla(\frac{1}{2}\|G\|^2)$ is the source's chosen robust route to the over-constrained minors system, not the unique admissible one; alternative certified formulations of the same criticality conditions are equally acceptable.

The unifying objective is to replace sampled point detection of criticality with a complete, certified description of the critical solution set within subdivision-based solving of multivariate piecewise polynomial systems. The application-specific post-process question of degeneracies introduced by mapping the parameter space into model/scene space is acknowledged in the source as per-application and remains outside this core.

References

1. Jonathan Mizrahi, Gershon Elber. Detection of critical points of multivariate piecewise polynomial systems. Computer Aided Geometric Design 40 (2015) 76–87. DOI 10.1016/j.cagd.2015.10.001. https://doi.org/10.1016/j.cagd.2015.10.001
2. Jonathan Mizrahi, Gershon Elber. Topologically guaranteed bivariate solutions of under-constrained multivariate piecewise polynomial systems. Computer-Aided Design 58 (2015) 210–219. DOI 10.1016/j.cad.2014.08.026. https://doi.org/10.1016/j.cad.2014.08.026
3. Jonathan Mizrahi, Sijoon Kim, Iddo Hanniel, Myung Soo Kim, Gershon Elber. Minkowski sum computation of B-spline surfaces. Graphical Models 91 (2017) 30–38. DOI 10.1016/j.gmod.2017.02.003. https://doi.org/10.1016/j.gmod.2017.02.003
4. Boris van Sosin, Gershon Elber. Solving piecewise polynomial constraint systems with decomposition and a subdivision-based solver. Computer-Aided Design 90 (2017) 37–47. DOI 10.1016/j.cad.2017.05.023. https://doi.org/10.1016/j.cad.2017.05.023
5. Daniel J. Bates, Jonathan D. Hauenstein, Chris Peterson, Andrew J. Sommese. A Numerical Local Dimension Test for Points on the Solution Set of a System of Polynomial Equations. SIAM Journal on Numerical Analysis 47 (2009) 3608–3623. DOI 10.1137/08073264X. https://doi.org/10.1137/08073264X
6. Daniel A. Brake, Jonathan D. Hauenstein, Alan C. Liddell. Validating the Completeness of the Real Solution Set of a System of Polynomial Equations. Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation (ISSAC 2016) 143–150. DOI 10.1145/2930889.2930910. https://doi.org/10.1145/2930889.2930910
7. Paul Breiding, Kemal Rose, Sascha Timme. Certifying Zeros of Polynomial Systems Using Interval Arithmetic. ACM Transactions on Mathematical Software 49 (2023). DOI 10.1145/3580277. https://doi.org/10.1145/3580277
8. Xiaohong Jia, Kai Li, Jinsan Cheng. Computing the Intersection of Two Rational Surfaces Using Matrix Representations. Computer-Aided Design 150 (2022) 103303. DOI 10.1016/j.cad.2022.103303. https://doi.org/10.1016/j.cad.2022.103303
9. Jin-San Cheng, Bingwei Zhang, Yikun Xiao, Ming Li. Topology driven approximation to rational surface-surface intersection via interval algebraic topology analysis. ACM Transactions on Graphics 42 (2023). DOI 10.1145/3592452. https://doi.org/10.1145/3592452
10. Jieyin Yang, Xiaohong Jia, Dong-Ming Yan. Topology Guaranteed B-Spline Surface/Surface Intersection. ACM Transactions on Graphics 42 (2023). DOI 10.1145/3618349. https://doi.org/10.1145/3618349