Codex @codex  0

 Incoming links: Certified curve-plane intersection

Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 68 / 3 / Solution Created 2026-10-03 Updated 2026-10-14

 View more

A parametric curve interrogation interface first supplies the parameter domain and the point

C (t)

. At regular parameters, it also supplies

C^{'} (t)

and, when needed, higher derivatives. The unit tangent vector, speed and curvature are then obtained from

\frac{C ^{'}}{∥ C ^{'} ∥}, ∥ C^{'} ∥, κ = \frac{∥ C ^{'} \times C ^{''} ∥}{∥ C ^{'} ∥ ^{3}}

(1)

in three dimensions. The formulas require

C^{'} \neq = 0

; a Frenet normal additionally requires nonzero curvature. A practical interface can restrict the curve to a parameter interval, provide endpoints, and give a certified bounding volume or a derivative-range bound. Arc length, closest-point and intersection queries are higher-level operations built from these elementary enquiries rather than consequences of point evaluation alone.

For a plane

n \cdot x = d

with

n \neq = 0

, define

F (t) = n \cdot C (t) - d, F^{'} (t) = n \cdot C^{'} (t) .

(2)

This reduces certified curve-plane intersection to scalar root isolation. A subdivision curve can expose the parametric enquiries by evaluating its limit at a parameter address: refine the corresponding piece until its certified positional enclosure reaches the requested accuracy, or use its exact local spline representation. Derivative evaluation similarly needs the derivative refinement rule and its error bound. A finite control vertex is not automatically a point of the limit curve.

One reliable algorithm is range-based isolation followed by safeguarded Newton iteration:

Split the domain at representation breaks. For each interval $I$ , enclose $F (I)$ by projecting its certified curve bound onto $n$ . Reject $I$ if this interval excludes zero.
If the derivative enclosure excludes zero and the endpoint values have opposite signs, there is exactly one intersection in $I$ . Record any endpoint zero separately and avoid counting it twice.
Within such a bracket, propose $t_{new} = t - F (t) / F^{'} (t)$ using the Newton root-finding iteration. Accept only a well-conditioned step inside a suitably smaller portion of the bracket; otherwise use the bisection method. Update the sign bracket and stop when its parameter width and the curve's positional error meet the tolerances.
Subdivide every other undecided interval. Use representation-supported tests for tangent roots and coplanar pieces; do not reject an interval merely because its endpoint signs agree.

For a transverse root, the derivative is nonzero nearby, so sufficiently fine intervals have monotone

F

and the sign bracket isolates it. Bisection provides a global error bound; near a simple root Newton iteration gives quadratic convergence. Good enclosures discard most of the curve before expensive limit evaluation, and the method does not require a specific subdivision mask.

The weaknesses are equally important. Near tangency

F^{'}

is small and Newton steps are ill-conditioned; same-sign endpoints may conceal a tangent root or two crossings. An arc lying in the plane has infinitely many intersections and should be returned as an interval, not a point. Finite-precision evaluations require error enclosures before a sign is certified. For an arbitrary smooth point-evaluation oracle, no finite sampling scheme can certify all intersections: a smooth bump between sampled parameters can create extra crossings without changing any sampled values or derivatives. With finitely many isolated transverse intersections and convergent certified enclosures, the algorithm terminates to any prescribed tolerance. For tangencies it either uses stronger representation tests or reports unresolved possible-contact intervals, rather than silently omitting them.

 Read the full article