= Solution
An efficient <parametric curve interrogation> interface should provide the parameter domain and open/closed status, point evaluation, one-sided endpoint enquiries, first and second <derivatives> wherever defined, and information about knots or singular parameters. It should also restrict a curve to an interval and subdivide it without changing its limit, return a certified <bounding volume> for that restriction, and supply derivative or <chord error bounds> when supported. These enquiries allow cheap geometric rejection before expensive exact evaluation. For a <subdivision curve>, limit evaluation is distinct from returning a vertex of a finite refined <control polygon>; the latter is usually an approximation.
For a query point $Q$, minimize $d(t)=\tfrac12\|P(t)-Q\|^2$. At a differentiable interior minimizer,
$$
\boxed{(P(t)-Q)\cdot P'(t)=0.}
$$
At a regular curve point this says that the query displacement is perpendicular to the <tangent vector>. If a second <derivative> exists, the local second-order test is
$$
d''(t)=\|P'(t)\|^2+(P(t)-Q)\cdot P''(t)\ge0;
$$
a strictly positive value is sufficient for a strict local minimum. The stationarity equation alone also includes local maxima and is automatic at $P'=0$, so it cannot be used as the only global search criterion.
A reliable efficient <closest-point search on a subdivision curve> uses <branch and bound>. Cover the compact curve by restricted pieces with certified enclosures $B_I$. For each piece set $L_I=\operatorname{dist}(Q,B_I)$, a lower bound on its true distance. Distances to actually evaluated limit points give upper bounds; keep the best point $P(t_*)$ and distance $U$. For an <axis-aligned bounding box> $\prod_k[l_k,h_k]$, the squared lower bound is inexpensive:
$$
L_I^2=\sum_k\bigl(\max\{l_k-Q_k,0,Q_k-h_k\}\bigr)^2.
$$
For positive partition-of-unity refinement, a <convex hull> of the active <control points> is an enclosure. A negative-weight scheme requires a separate certified enclosure; its control hull need not contain the limit.
The algorithm is:
* Initialize the pieces at representation breaks and evaluate endpoints and one or more interior limit points. Place pieces in a priority queue ordered by their $L_I$.
* Discard any piece with $L_I>U$, since it cannot improve the best known point. If only one nearest point is required, equality may also be discarded; keep equality candidates when all ties matter.
* Remove the smallest-bound piece. Evaluate new limit points to reduce $U$, subdivide the piece, compute tighter child enclosures, and insert children that can still improve $U$.
* Use the best chord projection or current candidate to seed a safeguarded <Newton root-finding iteration> for $F(t)=(P(t)-Q)\cdot P'(t)$. Its derivative is $F'(t)=\|P'\|^2+(P-Q)\cdot P''$. Keep iterates inside the restricted interval, fall back to <bisection method> on an isolated sign-changing bracket, and accept an improvement only after evaluating its actual curve distance. This is an accelerator; rejection still depends on certified geometric bounds.
* Terminate when $U-\min_I L_I\le\epsilon$, also regarding the best evaluated point as a retained candidate. If no pieces remain, the evaluated candidate is already optimal relative to the exhausted bounds. Return $t_*$ and $P(t_*)$ with the global distance guarantee.
Because $\min_I L_I\le d_{\min}\le U$, the reported point is at most $\epsilon$ farther from $Q$ than a true nearest point. Include endpoints, nondifferentiable joins, and singular parameters in the candidate bookkeeping, or split them into separate pieces. With enclosures converging in diameter under subdivision on a compact continuous curve, the bounds converge to arbitrary prescribed positive distance tolerance. Interval bounds or outward-rounded arithmetic are needed if the guarantee is intended to be certified in floating-point computation. A single <Newton root-finding iteration> from a single seed supplies no such global guarantee.
Back to article page
