Counterexamples to a Conjecture on First Derivative Bounds of Rational Bézier Curves

1. Problem Statement

The paper addresses the problem of estimating the maximum magnitude (supremum) of the first derivative, $\sup_{t \in [0,1]} \|r'(t)\|$, for rational Bézier curves. Accurate derivative bounds are critical for geometric modeling tasks such as adaptive subdivision, collision detection, and ensuring numerical stability.

The specific focus is on Conjecture 1, proposed by Li et al. (and supported by Zhang and Jiang), which suggests that for a rational Bézier curve of arbitrary degree $n$, the derivative bound is universally given by:
$$\|r'(t)\| \leq n M \max_{0 \leq i \leq n-1} \{ \|r_{i+1} - r_i\| \}$$
where:

• $r_i$ are the control points.
• $M$ is a weight variation measure defined as $M = \max \{ \max \frac{\omega_i}{\omega_{i+1}}, \max \frac{\omega_{i+1}}{\omega_i} \}$.
• This bound was previously proven valid for degrees $n=2$ and $n=3$.

The paper investigates whether this inequality holds for general degrees $n \geq 4$.

2. Methodology

The author employs a three-pronged methodological approach:

1. Counterexample Construction:

   • The author constructs a specific rational Bézier curve of degree $n=7$ with carefully chosen control points and weights.
   • The actual maximum derivative is computed via numerical optimization (using MATLAB's fminbnd), and compared against the value predicted by Conjecture 1.

2. Explicit Rational Representation of the Derivative:

   • Using Bernstein polynomial product formulas and degree-elevation techniques, the paper derives an explicit rational Bézier representation for the first derivative $r'(t)$.
   • The derivative $r'(t)$ is expressed as a rational curve of degree $2n$ (or higher after elevation), defined by new control points $Q^{[1]}_{i, 2n}$ and weights $\omega^{[1]}_{i, 2n}$.
   • This transformation allows the derivative to be analyzed using standard properties of rational Bézier curves.

3. Degree-Elevation Based Upper Bound:

   • The paper proposes a computable upper bound based on the degree elevation of the derivative representation.
   • By elevating the degree of the derivative curve from $2n$ to $2n+e$, the control polygon of the derivative converges uniformly to the actual derivative curve.
   • The maximum norm of the control points of the elevated derivative curve serves as an upper bound for the true supremum.
   • The paper establishes the convergence rate of this bound and provides a tolerance-driven criterion (Theorem 7) to determine the minimum elevation order $e$ required to achieve a user-specified error tolerance $\epsilon$.

3. Key Contributions

• Disproof of Conjecture 1: The paper provides a non-degenerate counterexample at degree $n=7$, proving that the conjectured bound is false in the general case.
  • Result: For the constructed example, the true maximum derivative is 7.7065, while the conjectured bound yields 7.7018.
• Explicit Derivative Formulation: The derivation of a closed-form rational Bézier representation for $r'(t)$ (Theorem 1) using Bernstein-product and degree-elevation formulas. This formulation is numerically reliable and admits a clear geometric interpretation.
• Convergent Upper Bound Algorithm: The proposal of a new algorithm (Theorem 2) that computes an upper bound for $\|r'(t)\|$ which is:
  • Valid for any finite elevation order $e$.
  • Guaranteed to converge to the true supremum as $e \to \infty$.
  • Converges at a rate of $O(1/(2n+e))$.
• Tolerance-Driven Degree Selection: The development of an a priori rule (Theorem 7) to calculate the minimal elevation degree $m$ required to ensure the computed bound is within a specific tolerance $\epsilon$ of the true supremum.
• Complexity Analysis: The paper analyzes the computational complexity, showing the method runs in $O(n^2d + (2n+1)(e+1)d)$ time, where $d$ is the dimension.

4. Results and Numerical Validation

The paper validates the proposed method through numerical experiments on a PC (Intel Core i7, 16GB RAM):

• Counterexample Verification: The $n=7$ example successfully demonstrates the failure of the conjecture.
• Performance Across Degrees (Example 2):
  • Tested degrees $n=2$ to $10$ with specific weight patterns ($\omega_i = 1.1^{|i-m|}$).
  • Accuracy: The proposed method consistently provided valid upper bounds that were very close to the true maximum (e.g., for $n=7$, true max 7.7065 vs. method bound 7.718).
  • Conjecture Failure: For $n \geq 7$, the true maximum derivative exceeded the conjectured bound.
  • Efficiency: Running times were negligible (milliseconds), and the method remained efficient even as the required degree elevation steps ($e$) increased to satisfy the tolerance.
• Alternative Weight Patterns (Example 3):
  • Tested degrees $n=2$ to $15$ with exponentially decaying weights.
  • The conjectured bound ($2n$) was significantly looser than the true maximum for higher degrees, while the proposed method provided tight, valid bounds.
  • The method maintained high computational efficiency with fixed elevation steps ($e=800$).

5. Significance and Future Work

Significance:

• Theoretical Correction: The paper corrects a misconception in the literature regarding derivative bounds for rational Bézier curves, preventing potential errors in algorithms relying on the false conjecture.
• Practical Utility: The proposed degree-elevation method offers a robust, computable, and convergent alternative for estimating derivative bounds, essential for safety-critical geometric applications.
• Algorithmic Framework: The derivation of the explicit derivative representation provides a foundation for analyzing higher-order derivatives and other properties of rational curves.

Open Problems Identified:

• Determining the exact maximum degree $n$ for which the conjecture remains valid (likely $n \leq 6$).
• Identifying specific conditions (e.g., monotone weights, bounded ratios) under which the conjecture might still hold for $n > 6$.
• Refining the relationship between the elevation number $e$ and the tolerance $\epsilon$ to make the selection of $e$ more efficient in practice, as the current theoretical bound is considered "loose."

In summary, this paper refutes a long-standing conjecture on rational Bézier derivative bounds and replaces it with a rigorous, convergent, and computationally efficient method based on degree elevation.