Certified topology of singular and inequality-trimmed two-dimensional solution sets of under-constrained piecewise polynomial systems

Subdivision solvers can now compute a two-dimensional solution manifold $Z = F^{-1}(0)\cap D$ of an under-constrained piecewise polynomial system $F:\mathbb{R}^n\to\mathbb{R}^{n-2}$ with a topological guarantee — each output patch is certified homeomorphic to the exact solution — but only under the assumption that $0$ is a regular value of $F$, i.e. the constraint gradients are linearly independent everywhere on $Z$. Mizrahi and Elber (Computer-Aided Design, 2015), who established this guarantee via a single-loop boundary test and an injective-projection test, stated as their main direction for future work the removal of this regularity assumption (first isolated singularities, then non-isolated critical loci), and, second, the incorporation of inequality constraints that trim the solution two-manifold without lowering its dimension. The authors' own follow-ups delivered detection of isolated critical points and inequality handling for zero- and one-dimensional solution sets only, leaving the topology of singular and trimmed two-manifolds unresolved; adjacent certified-meshing literature covers only nonsingular surfaces, singular plane curves, or singular hypersurfaces in $\mathbb{R}^3$. The problem — certify, with proven termination, the topology of the two-dimensional solution set when the regularity assumption fails and when the set is trimmed by inequalities — remains open.

Background

In geometric constraint solving one frequently meets under-constrained polynomial systems: maps $F:D\subset\mathbb{R}^n\to\mathbb{R}^{n-2}$, $n\ge 3$, on a compact box $D$, whose zero set $Z=F^{-1}(0)\cap D$ typically has two degrees of freedom. Examples include the configuration spaces of kinematic mechanisms with two degrees of freedom (two-DOF mechanisms), bisector surfaces (loci of points equidistant from two given geometric entities), and the boundaries of Minkowski sums (pointwise set sums) of free-form surfaces. In practice $F$ is piecewise polynomial, given in the B-spline basis (tensor-product spline functions whose pieces are polynomials glued with prescribed smoothness across knot lines).

A subdivision solver recursively splits $D$ into sub-domains, discarding sub-domains that can contain no solution (via the convex-hull property of spline control points: the graph of a spline lies in the convex hull of its control points) and terminating on the rest once a certificate is available; a numeric refinement step then builds a piecewise-linear (triangle-mesh) approximation. Guarantees come in two strengths: exclusion of spurious components, and topology guarantees, meaning the computed model is certified to be homeomorphic to (or an isotopic deformation of) the exact solution — same number of components, same boundary loops, same genus.

Topology-guaranteed subdivision was first achieved for zero-dimensional solution sets (Bartoň–Elber–Hanniel's cone test lineage, building on Hanniel–Elber's dual-hyperplane termination criteria) and one-dimensional solution sets (no-loop and single-component tests). Mizrahi and Elber (2015) extended this to two-dimensional solution sets: by the regular level set theorem, if $0$ is a regular value of $F$ — meaning the differential $dF_p$ is surjective at every $p\in Z$, equivalently the $n-2$ gradients $\nabla f_i$ are linearly independent on $Z$ — then $Z$ is an embedded two-manifold, and per sub-domain its topology can be certified as a closed disc using (a) the Single-Loop Boundary Test (the univariate solver must find that the solution's trace on the sub-domain boundary is a single simple loop) and (b) the Injective Projection Test (the solution must project one-to-one onto a coordinate two-plane, ruling out extra closed components and handles). These tests lean on normal/tangent cone bounds — double cones enclosing all normals or tangents of the hypersurfaces $f_i=0$ — which are computationally expensive, so that loose cones force deep subdivision.

The guarantee collapses when $0$ is not a regular value. Although Sard's theorem makes critical values measure-zero, tangential configurations (e.g. a sphere tangent to a plane) are common in real inputs. The published method only subdivides such regions down to the subdivision tolerance and returns them as bounded 'unknown' regions — detection and confinement, not resolution: no homeomorphism type is certified for the singular part. Inequality constraints $g_j(x)\ge 0$ (semi-algebraic restrictions) raise a further structural issue: they trim $Z$ to a smaller region, introducing new boundary curves that do not lie on $\partial D$, so the boundary-based termination machinery no longer applies as is. Related certified-meshing literature handles only special cases: Plantinga–Vegter and Lin–Yap–Yu mesh nonsingular implicit curves and surfaces isotopically; Burr–Choi–Galehouse–Yap achieve isotopic meshing of singular algebraic plane curves, and Diatta–Mourrain–Ruatta of a singular algebraic implicit surface in $\mathbb{R}^3$ — i.e. the single-hypersurface case, not general $(n-2)\times n$ under-constrained spline systems; Yang–Jia–Yan (2023) certified the topology of B-spline surface/surface intersection curves, a one-dimensional instance of the same paradigm.

Problem Statement

Let $F:D\subset\mathbb{R}^n\to\mathbb{R}^{n-2}$, $n\ge 3$, be a piecewise polynomial (B-spline) map on a compact box, with zero set $Z=F^{-1}(0)\cap D$. The framework of Mizrahi and Elber certifies the topology of a piecewise-linear model of $Z$ — each terminated sub-domain's model is certified homeomorphic to $Z$ intersected with that sub-domain — but only under the assumption that $0$ is a regular value of $F$ (the $n-2$ constraint gradients linearly independent at every solution point); regions violating the assumption are merely bounded to subdivision tolerance and returned as unknown. The problem, as posed by the source work, is to extend this certified framework beyond the regular case:

1. (Primary) Give an algorithm — subdivision-based or otherwise certified — with proven termination that computes a certified topological model of $Z$ when $0$ is not a regular value of $F$: first in the presence of isolated critical points on $Z$, where the algorithm must identify the local topological type of the solution at the singularity (up to homeomorphism) rather than merely bound it; and then in the presence of non-isolated critical loci, where $Z$ need not be a manifold at all and the local topological models of the solution near such loci must be classified and certified.

2. (Second component of the same extension) Incorporate inequality constraints $g_j(x)\ge 0$ (piecewise polynomial, in the same B-spline framework as $F$) that trim the two-manifold without reducing its dimension: certify the topology of the trimmed set $Z\cap\{g\ge 0\}$.

The extension comprises both components: a certified resolution when $0$ is not a regular value of $F$ (first the isolated-critical-point case, then non-isolated critical loci) and certification of the topology of the inequality-trimmed set $Z\cap\{g\ge 0\}$.

Any proposed solution should preserve the practical character of the framework: termination tests whose cost is governed by normal/tangent cone bounds (tighter cone and piecewise-linear approximation bounds are stated quality desiderata of the source work, not part of the completion boundary), and applicability to spline input and to the motivating applications such as kinematic configuration spaces of two-degree-of-freedom mechanisms, bisector surfaces, and Minkowski-sum boundaries.

References

1. 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 (author preprint for the Geometric Modeling and Processing (GMP) 2014 conference: https://www.cs.technion.ac.il/~gershon/papers/MVBivarSolver.pdf)
2. 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
3. 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 (author preprint: https://www.cs.technion.ac.il/~gershon/papers/mv_solver_decomp2017.pdf)
4. 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
5. Michael Bartoň, Gershon Elber, Iddo Hanniel, 'Topologically guaranteed univariate solutions of underconstrained polynomial systems via no-loop and single-component tests', Computer-Aided Design 43 (8) (2011) 1035–1044. DOI: 10.1016/j.cad.2011.03.009, https://doi.org/10.1016/j.cad.2011.03.009
6. Iddo Hanniel, Gershon Elber, 'Subdivision termination criteria in subdivision multivariate solvers using dual hyperplanes representations', Computer-Aided Design 39 (5) (2007) 369–378. DOI: 10.1016/j.cad.2007.02.004, https://doi.org/10.1016/j.cad.2007.02.004
7. Jieyin Yang, Xiaohong Jia, Dong-Ming Yan, 'Topology Guaranteed B-Spline Surface/Surface Intersection', ACM Transactions on Graphics 42 (6) (2023) 1–16. DOI: 10.1145/3618349, https://doi.org/10.1145/3618349
8. Michael Burr, Sung Woo Choi, Ben Galehouse, Chee K. Yap, 'Complete subdivision algorithms, II: Isotopic meshing of singular algebraic curves', Journal of Symbolic Computation 47 (2) (2012) 131–152. DOI: 10.1016/j.jsc.2011.08.021, https://doi.org/10.1016/j.jsc.2011.08.021
9. Daouda Niang Diatta, Bernard Mourrain, Olivier Ruatta, 'On the isotopic meshing of an algebraic implicit surface', Journal of Symbolic Computation 47 (8) (2012) 903–925. DOI: 10.1016/j.jsc.2011.09.010, https://doi.org/10.1016/j.jsc.2011.09.010
10. Simon Plantinga, Gert Vegter, 'Isotopic approximation of implicit curves and surfaces', Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing (2004) 245–254. DOI: 10.1145/1057432.1057465, https://doi.org/10.1145/1057432.1057465
11. Long Lin, Chee Yap, Jihun Yu, 'Non-local isotopic approximation of nonsingular surfaces', Computer-Aided Design 45 (2) (2013) 451–462. DOI: 10.1016/j.cad.2012.10.028, https://doi.org/10.1016/j.cad.2012.10.028