Bivariate range functions with superior convergence order

1. Problem Statement

In geometric modeling, computer graphics, and robotics, range functions (or inclusion functions) are essential for certified computations such as root finding, surface intersection, and collision detection. A range function $\bar{f}(B)$ must enclose the true range of a function $f$ over a domain $B$ (typically a box).

The efficiency of algorithms using these functions (e.g., branch-and-bound) depends on two factors:

1. Efficiency: How fast the range is evaluated.
2. Efficacy (Tightness): How close the estimated range is to the true range.

The Core Issue: Traditional range functions based on Taylor expansions or natural interval extensions typically exhibit quadratic convergence ($m=2$). This means the error decreases proportionally to the square of the domain width ($w(B)^2$). While higher-order Taylor expansions exist, they often fail to improve the convergence order beyond 2 due to the limitations of standard interval arithmetic. The paper aims to develop bivariate range functions with superior convergence orders ($m > 2$, specifically cubic $m=3$ and quartic $m=4$) to achieve tighter bounds without sacrificing too much computational efficiency.

2. Methodology

The authors build upon the Cornelius–Lohner (CL) framework, generalized by Hormann et al. (2023). The core idea is to split the function $f$ into an "exact" part $g$ and a "remainder" part $R_g$:
$$f(x) = g(x) + R_g(x)$$
The range is then estimated as $\bar{f}(B) = \bar{g}(B) + \bar{R}_g(B)$. To achieve superior convergence, the remainder term must be bounded tightly (order $m$), and the exact part $g$ must be handled such that its approximation error does not degrade the overall order.

The paper proposes three novel bivariate range functions based on different interpolation strategies:

A. Centered Taylor Expansion (Section 2)

• Approach: Generalizes the standard centered Taylor form. The function is expanded around the midpoint of the box.
• Mechanism: The first $m$ terms of the Taylor polynomial are treated as the "exact" part $g$ (whose range is computed exactly or tightly), and the remaining terms form the remainder $R_g$.
• Result: By splitting the polynomial at degree $m-1$, the method achieves order $m$ convergence.
• Forms: Specifically introduces $T_{m,n}$ forms for $m=2, 3, 4$.

B. Recursive Lagrange Form (Section 3)

• Approach: Inspired by univariate recursive Lagrange interpolation.
• Mechanism:
  1. Approximates $f$ using a biquadratic Lagrange polynomial ($L_{0,0}$) interpolating $f$ at a $3 \times 3$ grid (corners, edge midpoints, center).
  2. The error bound depends on third-order partial derivatives.
  3. These derivatives are recursively bounded using the same Lagrange interpolation strategy.
  4. The "exact" part is the quadratic Taylor expansion of the interpolant; the remainder is bounded by a series involving Delannoy numbers (Tribonacci triangle coefficients).
• Result: Achieves cubic convergence ($m=3$).

C. Recursive Hermite Form (Section 4)

• Approach: Extends univariate recursive Hermite interpolation to the bivariate case.
• Mechanism:
  1. Approximates $f$ using a bicubic Hermite polynomial ($H_{0,0}$) interpolating $f$ and its first partial derivatives at the four corners of the box.
  2. The error bound depends on fourth-order partial derivatives.
  3. Similar to the Lagrange form, higher-order derivatives are bounded recursively.
• Result: Achieves quartic convergence ($m=4$).

3. Key Contributions

1. Novel Bivariate Forms: Introduction of the first practical bivariate range functions with cubic ($m=3$) and quartic ($m=4$) convergence orders, based on Taylor, Lagrange, and Hermite interpolations.
2. Theoretical Proofs: Rigorous proofs (Theorems 3, 4, and 5) demonstrating that these forms satisfy the generalized Cornelius–Lohner framework and achieve the claimed convergence orders.
3. Implementation in Julia: The authors implemented these algorithms in Julia using Straight-Line Programs (SLPs) and automatic differentiation techniques to handle polynomial evaluation efficiently.
4. "Sweet Spot" Identification: Through extensive experimentation, the paper identifies cubic convergence ($m=3$) as the optimal trade-off between efficiency and efficacy for practical applications.

4. Experimental Results

The authors tested the methods on four polynomial test functions (e.g., "clover-4", "grass") over a subdivided grid of 1024 boxes.

• Convergence Verification: Log-log plots of the Hausdorff distance ($d_H$) vs. box radius ($r$) confirmed the theoretical convergence slopes:
  • $T_2$: $O(r^2)$
  • $T_3, L_3$: $O(r^3)$
  • $T_4, H_4$: $O(r^4)$
• Efficacy (Tightness):
  • All superior-order methods ($m \ge 3$) provided significantly tighter bounds than the baseline quadratic Taylor form ($T_2$).
  • Efficacy ratios (tightness improvement) ranged from 1.19 to 1.30.
  • $L_3$ was consistently tighter than $T_3$ for small box sizes.
• Efficiency (Speed & Memory):
  • Taylor Forms ($T_3, T_4$): Had execution times very similar to the baseline $T_2$ (speedup ratios $\approx 0.84 - 1.07$), making them highly efficient.
  • Lagrange/Hermite Forms (Without Sharing): Were significantly slower (speedup ratios $0.36 - 0.61$) and used more memory due to the need to evaluate derivatives at multiple grid points.
  • Lagrange/Hermite Forms (With Sharing): When computations (function and derivative evaluations at grid nodes) were shared across adjacent boxes in a subdivision algorithm, the Lagrange form ($L_3$) became the most efficient method, outperforming even the baseline Taylor form in speed and memory usage.
• The "Sweet Spot": The experiments suggest that moving from $m=3$ to $m=4$ yields diminishing returns. The quartic forms ($H_4$) were generally slower and more complex to implement, offering only marginally tighter bounds compared to cubic forms.

5. Significance

• Advancement in Certified Computing: This work bridges the gap between theoretical superior convergence and practical implementation for bivariate functions, enabling more robust and faster root-finding and curve-tracing algorithms.
• Practical Optimization: By identifying cubic convergence as the "sweet spot," the paper guides practitioners to use $L_3$ (with data sharing) or $T_3$ for the best balance of speed and accuracy.
• Foundation for Future Work: The framework is extensible to higher dimensions and higher orders. The authors note that while the theory applies to general analytic functions, the current implementation focuses on polynomials, with plans to extend to general functions and integrate these methods into full subdivision-based curve tracing pipelines.

In summary, the paper successfully demonstrates that superior convergence order is achievable in bivariate settings and that cubic convergence via recursive Lagrange interpolation (with shared data) offers the most practical advantage for geometric modeling applications.