Bivariate range functions with superior convergence order Journal: GMP 2026 To appear in GMP 2026 Proceedings. This arXiv version has additional experimental data in Appendix C.
Bingwei Zhang, Thomas Chen, Kai Hormann, Chee Yap · 2026
Read Bivariate range functions with superior convergence order Journal: GMP 2026 To appear in GMP 2026 Proceedings. This arXiv version has additional experimental data in Appendix C. by Bingwei Zhang, Thomas Chen, Kai Hormann, Chee Yap (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-14400.txt.
Introduction
Zhang, Chen, Hormann, and Yap build new bivariate range functions with better-than-quadratic convergence for certified geometric computation. Traditional range functions converge only quadratically, so the team exploits the Cornelius-Lohner framework with Taylor, Lagrange, and Hermite interpolation. The team focuses on usable cubic and quartic variants, implemented in Julia with tests of speed and quality. The higher-order functions give certified work a sharper tool for models, graphics, and robots.
Catalog record
| CREATOR | Bingwei Zhang, Thomas Chen, Kai Hormann, Chee Yap |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 81658 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.14400
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Bivariate range functions with superior convergence order Journal: GMP 2026 To appear in GMP 2026 Proceedings. This arXiv version has additional experimental data in Appendix C. Bingwei Zhang, Thomas Chen, Kai Hormann, Chee Yap Abstract Range functions are a fundamental tool for certified computations in geometric modeling, computer graphics, and robotics, but traditional range functions have only quadratic convergence order ( m = 2 m=2 ). For “superior” convergence order (i.e., m > 2 m>2 ), we exploit the Cornelius–Lohner framework in order to introduce new bivariate range functions based on Taylor, Lagrange, and Hermite interpolation. In particular, we focus on practical range functions with cubic and quartic convergence order. We implemented them in Julia and provide experimental validation of their performance in terms of efficiency and efficacy. 1 Introduction Many problems in geometric modeling, computer graphics, and robotics, such as surface-surface intersection, constructive solid geometry (CSG) operations, ray-tracing, and collision detection, can be solved robustly using interval analysis and range (or inclusion) functions [ 5 , 24 , 10 ] . The core idea of range functions is to calculate an interval that is guaranteed to enclose the range of a function f over any given domain B , where B is typically a box, simplex, or ball in Euclidean space [ 21 ] . Range functions provide various certified predicates for finding roots of f . One such predicate is the exclusion predicate of root finding: if the estimated range of f over B does not contain zero, then f has no roots in B . With good range functions, provably near-optimal complexity bounds can be achieved for isolating real and complex roots [ 22 , 4 ] . Combined with subdivision, range functions lead to very efficient branch-and-bound algorithms for the problems mentioned before [ 17 , 23 ] . In particular, bivariate range functions have been used for the isotopic approximation of curves [ 20 , 1 , 2 ] , and they can be used for finding the roots of mappings from \mathbb{R}^{2} to \mathbb{R}^{2} [ 6 ] . Clearly, the efficiency of these algorithms depends on (1) the efficiency of evaluating the range functions and (2) the efficacy (or tightness) of the estimated ranges. A simple measure of tightness is the order of convergence. The classic approach to range functions for f is based on the Taylor expansion of f to some degree n\geq 1 . Unfortunately, the order of convergence remains quadratic ( m=2 ), regardless of n [ 21 ] . 8 introduced the “CL framework” that finally achieves superior convergence orders (i.e., m>2 ). While they can only reach convergence orders of up to m\leq 6 , due to the underlying implicit computational model, 14 showed how to achieve convergence order m for any m>1 by generalizing the CL framework. Superior convergence orders have an efficiency cost. So in any application, one must choose a “sweet spot” convergence order that achieves practical trade-offs among efficiency, efficacy, and ease of implementation. Typically, the sweet spot is some small m , say m<6 . E.g., for the EVAL root isolation algorithm [ 13 ] , such considerations led to the sweet spot order of m=3 . Thus, in our current implementations, we focus on convergence orders up to m\leq 4 . Although our techniques are in principle able to reach larger values of m , it is clear from our development below that their implementation will be much more involved. In this paper, we focus on the bivariate setting and derive new range functions that advance the state of the art in terms of convergence order. Specifically, we introduce bivariate range functions with cubic and quartic convergence orders that are based on Taylor, Lagrange, and Hermite interpolation. The geometric modeling literature has a well-known “Bernstein range” for any polynomial f over a box B , namely the interval between the minimum and maximum Bernstein coefficients over B [ 11 ] . But our experiments will not compare this Bernstein range function with our range functions. We offer two justifications for this omission. First, the Bernstein approach is fundamentally different from the interpolation approach of our methods, since it works only for polynomials and we know of no range functions based on the Bernstein approach with a superior convergence order. Second, the comprehensive study of 17 compared a set of 30 range functions for tracing planar curves, and they concluded that the Bernstein method performs comparably to the centered form Taylor method, but the latter is easier to implement. This centered form Taylor method is just {\!\;\framebox{\phantom{$I$\!\!\,}}\!\;}^{T}_{2,n} in our experiments. 1.1 Range functions For any bivariate real function f\colon\mathbb{R}^{2}\to\mathbb{R} and any S\subseteq\mathbb{R}^{2} , the range of f on S is the set f(S)\mathrel{:=}\{f(x):x\in S\} . With {\!\;\framebox{\phantom{$I$\!\!\,}}\!\;}\mathbb{R}^{2} denoting the set of closed, axis-aligned rectangles, also called boxes and {\!\;\framebox{\phantom{$I$\!\!\,}}\!\;}\mathbb{R} denoting the set of closed intervals, we call {\!\;\framebox{\phantom{$I$\!\!\,}}\!\;}f\colon{\!\;\framebox{\phantom{$I$\!\!\,}}\!\;}\mathbb{R}^{2}\to{\!\;\framebox{\phantom{$I$\!\!\,}}\!\;}\mathbb{R} a range function for f , if {\!\;\framebox{\phantom{$I$\!\!\,}}\!\;}f(B)\supseteq f(B) for all B\in{\!\;\framebox{\phantom{$I$\!\!\,}}\!\;}\mathbb{R}^{2} . For any box B=[a_{x},b_{x}]\times[a_{y},b_{y}]\in{\!\;\framebox{\phantom{$I$\!\!\,}}\!\;}\mathbb{R}^{2} , the midpoint , radius , and (maximal) width of B are defined as \bm{m}=(m_{x},m_{y})\mathrel{:=}(a_{x}+b_{x},a_{y}+b_{y})/2 , \bm{r}=(r_{x},r_{y})\mathrel{:=}(b_{x}-a_{x},b_{y}-a_{y})/2 , and w(B)\mathrel{:=}2\max(r_{x},r_{y}) .We further define the width and the magnitude of any I=[a,b]\in{\!\;\framebox{\phantom{$I$\!\!\,}}\!\;}\mathbb{R} as w(I)\mathrel{:=}b-a and {\lvert{I}\rvert}\mathrel{:=}\max\{{\lvert{a}\rvert},{\lvert{b}\rvert}\} . For any m\geq 1 , we say that the range function {\!\;\framebox{\phantom{$I$\!\!\,}}\!\;}f exhibits order m convergence on B_{0}\in{\!\;\framebox{\phantom{$I$\!\!\,}}\!\;}\mathbb{R}^{2} , if there exists a constant C>0 that may depend on f and B_{0} , such that \Hausdorff(f(B),{\!\;\framebox{\phantom{$I$\!\!\,}}\!\;}f(B))\leq C{w(B)}^{m} (1) for all B\subset B_{0} , where \Hausdorff([a,b],[a^{\prime},b^{\prime}])\mathrel{:=}\max\{{\lvert{a-a^{\prime}}\rvert},{\lvert{b-b^{\prime}}\rvert}\} denotes the Hausdorff distance between intervals. For a rational function f , given in terms of a specific expression (or formula ) E(x,y) , the simplest range function over B=I\times J with I,J\in{\!\;\framebox{\phantom{$I$\!\!\,}}\!\;}\mathbb{R} is the natural interval extension [ 18 , Section 3.3] {\!\;\framebox{\phantom{$I$\!\!\,}}\!\;}f(B)\mathrel{:=}E(I,J) , obtained by replacing the variables with intervals and utilizing interval arithmetic during the evaluation of the expression E . If {\!\;\framebox{\phantom{$I$\!\!\,}}\!\;}f(B) is well-defined for all B\subseteq B_{0} , then {\!\;\framebox{\phantom{$I$\!\!\,}}\!\;}f is convergent over B_{0} [ 18 , Chapter 4] , but the convergence is only of order 1 in general. Quadratic convergence is instead achieved by centered forms , for example, the celebrated mean-value form [ 21 , Chapter 3] . The breakthrough to achieve range functions with superior convergence comes from the CL Framework [ 8 ] . The idea is to split f into two parts f(x)=g(x)+R_{g}(x) where g is called the exact part and R_{g}\mathrel{:=}f-g the remainder part , and for any interval I , we compute g(I) exactly while R_{g}(I) can be approximated by some range function {\!\;\framebox{\phantom{$I$\!\!\,}}\!\;}R_{g}(I) : Theorem 1 ( 8 , 8 , Theorem 4) . If the function f\colon\mathbb{R}\to\mathbb{R} is continuous over I_{0}\in{\!\;\framebox{\phantom{$I$\!\!\,}}\!\;}\mathbb{R} and can be written as f(x)=g(x)+R_{g}(x) for any x\in I_{0} , then the range function {\!\;\framebox{\phantom{$I$\!\!\,}}\!\;}f(I)\mathrel{:=}g(I)+{\!\;\framebox{\phantom{$I$\!\!\,}}\!\;}R_{g}(x) (2) satisfies \Hausdorff(f(I),{\!\;\framebox{\phantom{$I$\!\!\,}}\!\;}f(I))\leq w({\!\;\framebox{\phantom{$I$\!\!\,}}\!\;}R_{g}(I)) for any I\subseteq I_{0} . In particular, the convergence order of {\!\;\framebox{\phantom{$I$\!\!\,}}\!\;}f(I) is that of {\!\;\framebox{\phantom{$I$\!\!\,}}\!\;}R_{g}(I) , and we know how to achieve superior convergence orders for {\!\;\framebox{\phantom{$I$\!\!\,}}\!\;}R_{g} . The problem with ( 2 ) is that there are no 1 1 1 8 assumed that if we have an algebraic expression for g(x) , then we can compute its roots exactly. E.g., if g(x) is a polynomial of degree at most