Jüttler and Chalmovianský (AAECC 2007) approximated a segment of the intersection curve of two implicitly defined surfaces by a rational parametric curve via a predictor–corrector scheme with an SQP-type corrector, and bounded the Hausdorff distance between the algebraic intersection curve and its rational approximation — but their certification, based on Bernstein-basis bounding of the constants of the bound theorem, is available only when both defining functions are polynomials. Their conclusion leaves open: exploiting algebraic-space-curve topology analysis for certified segment selection, global connectivity, and spurious-branch avoidance; a generally applicable computable certification for non-polynomial C^3 implicit functions; and a priori distance bounds depending only on pre-optimization geometric data. The problem is therefore open: build a certified approximate-parameterization pipeline (correct topology, computable error constants, and a priori bounds) for implicit surface intersections in the full C^3 generality of the source paper.

Background

The intersection of two surfaces — the surface/surface intersection (SSI) problem — is one of the most heavily used routines in computer-aided design (CAD), geometric modeling, and mesh generation: trimming, Boolean operations, and boundary evaluation all reduce to computing the curve where two surfaces meet. When both surfaces are given implicitly, as the zero sets f(x,y,z)=0f(x,y,z)=0 and g(x,y,z)=0g(x,y,z)=0 of two scalar functions, their intersection is generically a space curve, the set where f=g=0f=g=0, which has no closed-form parameterization in general. A common practical goal is therefore approximate parameterization: represent the intersection curve, or a segment of it, by a rational parametric curve (a curve whose coordinate functions are quotients of polynomials), which downstream CAD data structures can store and evaluate exactly. Jüttler and Chalmovianský (2007) proposed a predictor–corrector technique for this task: predictor steps (by extrapolation or by integrating the differential equation governing the intersection curve) advance along the curve, and a corrector step — sequential quadratic programming (SQP), i.e. iterative optimization of a quadratic model of the objective — minimizes an objective approximating the integral of the squared Euclidean distance from the approximating curve to the intersection curve. To certify accuracy they bound the Hausdorff distance (the maximal distance from any point of one set to the nearest point of the other, and vice versa) between the intersection curve and its rational approximation by a theorem whose constants encode distance and gradient bounds on ff and gg. These constants can be computed when f,gf,g are polynomials, because a polynomial over a box can be re-expressed in the Bernstein basis (a polynomial basis whose coefficients tightly bracket the function's range), the so-called BB strategy; for general non-polynomial C3C^3 functions no corresponding generally applicable, computable certification was given. Their conclusion lists as open: (i) exploiting symbolic topology analysis of algebraic space curves (real curves defined by polynomial equations, whose topological type could then be computed, e.g. by Alcázar and Sendra, 2005) to guide segment selection, global connectivity, and spurious-branch avoidance in a certified manner; (ii) computing the certification constants for non-polynomial C3C^3 implicit functions; and (iii) deriving a priori distance bounds — bounds predictable from local geometric data known before the optimization — rather than the a posteriori estimates extracted from the produced curve. Later literature resolved the algebraic subcase and the parametric-surface analogue of these items. For intersections of two algebraic (polynomial implicit) surfaces, certified symbolic-numeric algorithms now exist: Diatta, Mourrain and Ruatta (2008) compute the topology of non-reduced implicit space curves with an isotopic piecewise-linear output; Cheng, Jin and Lazard (2013) produce certified G1G^1 (tangent-continuous) rational approximations of real algebraic space curves that have the same topology and Hausdorff distance below any prescribed tolerance; Jin and Cheng (2014, 2020) give isotopic epsilon-meshing; Cheng, Jin, Pouget, Wen and Zhang (2024) sharpen the complexity; and Liang, Mourrain and Pavone (2008) give subdivision-based topology of 2D and 3D implicit curves. For parametric surfaces (rational, B-spline, and NURBS — non-uniform rational B-splines, the industry-standard parametric surface representation), topology-guaranteed intersection algorithms appeared in 2012–2026 (Shen, Cheng and Jia; Yang, Jia and Yan; Cheng, Zhang, Xiao and Li; Zhang, Cheng, Liu and Zhang), and Li, Wu, Luo, Na and Cheng (2026) achieve a priori precision control of the Hausdorff distance for NURBS SSI via Lipschitz continuity and convex-hull arguments. Interval and validated-ODE methods (Hu, Maekawa, Patrikalakis and Ye, 1997; Ko and Ahn, 2010) can trace intersections of general smooth surfaces with validated enclosures during marching. What no published method provides is the combination the source paper asked for in the non-algebraic implicit setting: a generally applicable, computable certificate — correct topology together with Hausdorff-distance bounds and a priori error bounds — for a parametric approximation of the intersection curve of two general C3C^3 implicitly defined surfaces.

Problem Statement

Let Ω⊂R3\Omega\subset\mathbb{R}^3 be a given bounded region of interest (for example a closed box), and let f,g:R3→Rf,g:\mathbb{R}^3\to\mathbb{R} be C3C^3 functions, not assumed to be polynomials, defining two implicitly defined surfaces. Assume the intersection is transversal on Ω\Omega: at every point of the intersection set C={(x,y,z)∈Ω:f(x,y,z)=g(x,y,z)=0}C=\{(x,y,z)\in\Omega : f(x,y,z)=g(x,y,z)=0\}, the gradients ∇f\nabla f and ∇g\nabla g are linearly independent, so that — by the implicit function theorem — CC is a smooth curve (a finite collection of smooth curve components within the region). The problem is to produce a certified approximate parameterization of CC: explicit parametric (e.g. rational) curves approximating CC, together with a machine-computable certificate that guarantees the following three properties. (1) Topology: every connected component of CC in the region is represented exactly once, connectivity is preserved (for example, the output is isotopic to CC within the region, i.e. related to CC by a continuous deformation), and no spurious branches are produced — certified without assuming that f,gf,g are algebraic. (2) Error: a computable bound on the Hausdorff distance (the maximal distance from any point of one set to the nearest point of the other set, and vice versa) between CC and the approximation — a directly computable certificate of the kind the source paper obtained, in the polynomial case only, by Bernstein-basis bounding of the distance and gradient constants of its Hausdorff-distance theorem, but by means that are valid for general non-polynomial C3C^3 implicit functions, for which Bernstein-basis bounding is unavailable. (3) A priori bounds: an error bound that depends only on local geometric quantities of f,gf,g and of CC (such as curvature, transversality or conditioning) together with pre-chosen algorithmic parameters such as the step size — all available before the approximation or optimization is performed, rather than only a posteriori estimates extracted from the output. The algebraic (polynomial) subcase, for which certified symbolic-numeric algorithms have existed since 2008-2013, is not the open content; the open content is certification for general non-polynomial C3C^3 implicit surfaces, as left open by the source paper.

References

  1. Bert Jüttler, Pavel Chalmovianský: A predictor–corrector-type technique for the approximate parameterization of intersection curves. Applicable Algebra in Engineering, Communication and Computing 18(1-2):151-168, 2007. DOI: 10.1007/s00200-006-0031-8. URL: https://doi.org/10.1007/s00200-006-0031-8
  2. Juan Gerardo Alcázar, J. Rafael Sendra: Computation of the topology of real algebraic space curves. Journal of Symbolic Computation 39(6):719-744, 2005. DOI: 10.1016/j.jsc.2005.01.006. URL: https://doi.org/10.1016/j.jsc.2005.01.006
  3. Daouda Niang Diatta, Bernard Mourrain, Olivier Ruatta: On the computation of the topology of a non-reduced implicit space curve. In Proceedings of the 21st International Symposium on Symbolic and Algebraic Computation (ISSAC 2008), pages 47-54, 2008. DOI: 10.1145/1390768.1390778. URL: https://doi.org/10.1145/1390768.1390778 (preprint: arXiv:0803.1110, https://arxiv.org/abs/0803.1110)
  4. Jin-San Cheng, Kai Jin, Daniel Lazard: Certified rational parametric approximation of real algebraic space curves with local generic position method. Journal of Symbolic Computation 58:18-40, 2013. DOI: 10.1016/j.jsc.2013.06.004. URL: https://doi.org/10.1016/j.jsc.2013.06.004 (preprint: arXiv:1204.0905, https://arxiv.org/abs/1204.0905, which additionally lists Xiao-Shan Gao among the authors)
  5. Kai Jin, Jin-San Cheng: Isotopic epsilon-meshing of real algebraic space curves. In Proceedings of the 2014 Symposium on Symbolic-Numeric Computation (SNC 2014), pages 118-127, 2014. DOI: 10.1145/2631948.2631970. URL: https://doi.org/10.1145/2631948.2631970
  6. Kai Jin, Jinsan Cheng: Isotopic Meshing of a Real Algebraic Space Curve. Journal of Systems Science and Complexity 33:1275-1296, 2020. DOI: 10.1007/s11424-020-8378-7. URL: https://doi.org/10.1007/s11424-020-8378-7
  7. Jin-San Cheng, Kai Jin, Marc Pouget, Junyi Wen, Bingwei Zhang: An improved complexity bound for computing the topology of a real algebraic space curve. Journal of Symbolic Computation 125:102309, 2024. DOI: 10.1016/j.jsc.2024.102309. URL: https://doi.org/10.1016/j.jsc.2024.102309
  8. Chen Liang, Bernard Mourrain, Jean-Pascal Pavone: Subdivision Methods for the Topology of 2d and 3d Implicit Curves. In Geometric Modeling and Algebraic Geometry, Springer, pages 199-214, 2008. DOI: 10.1007/978-3-540-72185-7_11. URL: https://doi.org/10.1007/978-3-540-72185-7_11
  9. Sonia L. Rueda, Juana Sendra, J. Rafael Sendra: An algorithm to parametrize approximately space curves. Journal of Symbolic Computation 56:80-106, 2013. DOI: 10.1016/j.jsc.2013.04.002. URL: https://doi.org/10.1016/j.jsc.2013.04.002 (preprint: arXiv:1107.1584, https://arxiv.org/abs/1107.1584, titled 'Approximate Parametrization of Space Algebraic Curves')
  10. Michal Bizzarri, Miroslav Lávička: A symbolic-numerical approach to approximate parameterizations of space curves using graphs of critical points. Journal of Computational and Applied Mathematics 242:107-124, 2013. DOI: 10.1016/j.cam.2012.10.015. URL: https://doi.org/10.1016/j.cam.2012.10.015
  11. Li-Yong Shen, Jin-San Cheng, Xiaohong Jia: Homeomorphic approximation of the intersection curve of two rational surfaces. Computer Aided Geometric Design 29(8):613-625, 2012. DOI: 10.1016/j.cagd.2012.02.005. URL: https://doi.org/10.1016/j.cagd.2012.02.005
  12. Jieyin Yang, Xiaohong Jia, Dong-Ming Yan: Topology Guaranteed B-Spline Surface/Surface Intersection. ACM Transactions on Graphics 42(6), 2023. DOI: 10.1145/3618349. URL: https://doi.org/10.1145/3618349
  13. 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(4), 2023. DOI: 10.1145/3592452. URL: https://doi.org/10.1145/3592452
  14. Bingwei Zhang, Jin-San Cheng, Yu-Shen Liu, Zhaoqi Zhang: Topology guaranteed and error controlled curve tracing for parametric surface-surface intersection. Computer Aided Geometric Design 118:102432, 2025. DOI: 10.1016/j.cagd.2025.102432. URL: https://doi.org/10.1016/j.cagd.2025.102432
  15. Gangyi Li, Xi Wu, Zhongxuan Luo, Lei Na, Jin-San Cheng: A Precision Controlled Surface-Surface Intersection Algorithm for NURBS. ACM Transactions on Graphics 45(5):1-14, 2026. DOI: 10.1145/3806045. URL: https://doi.org/10.1145/3806045
  16. K. H. Ko, H. S. Ahn: Approximation of 3D surface-to-surface intersection curves. Engineering with Computers 26(1):49-60, 2010 (online 2009). DOI: 10.1007/s00366-009-0133-6. URL: https://doi.org/10.1007/s00366-009-0133-6
  17. C.-Y. Hu, T. Maekawa, N. M. Patrikalakis, X. Ye: Robust interval algorithm for surface intersections. Computer-Aided Design 29(9):617-627, 1997. DOI: 10.1016/S0010-4485(96)00099-1. URL: https://doi.org/10.1016/S0010-4485(96)00099-1