 Endpoint certificate for continuous collision clearance

An endpoint certificate for continuous collision clearance uses distances at two sampled configurations and a bound on intervening motion to prove separation for an entire time interval. Its guarantee concerns every intermediate configuration, rather than only the sampled poses.

Let $d(t)\ge 0$ be the set distance between a moving nonempty compact set and fixed nonempty closed set of obstacles, with $0\le t\le h$. Suppose $|d(t)-d(s)|\le L|t-s|$, with $L\ge 0$, and let the exact endpoint distances be $d_0,d_1$. The two endpoint inequalities implyThis uses a valid clearance Lipschitz continuity constant, such as the rigid-body motion bound derived in angular clearance bound for a rotating body. The continuous-path requirement itself is fundamental to the primary planning model.^[ref]

For $L>0$ and consistent endpoint data $|d_1-d_0|\le Lh$, the two sloping bounds intersect atTheir maximum is minimized there, giving the sharp general lower boundIt is sharp among nonnegative functions with that Lipschitz continuity bound and those endpoints: the displayed envelope itself satisfies the assumptions. This does not say that the unknown actual trajectory attains the lower bound.

For an original example, take $d_0=12\mathrm{mm}$, $d_1=20\mathrm{mm}$, $L=100mm/s$ and $h=0.1\mathrm{s}$. Since $Lh=10\mathrm{mm}$, the simple nearest-endpoint certificate gives $\min (d_0,d_1)-Lh/2=7\mathrm{mm}$. The paired bounds give $(12+20-10)/2=11\mathrm{mm}$, with their intersection at $t_{\ast }=0.01\mathrm{s}$. Thus the sharper certificate proves separation greater than a $10\mathrm{mm}$ required clearance margin where the simpler one does not.

For $L=0$, consistency requires $d_0=d_1$, and the clearance is constant. An endpoint difference larger than $Lh$ contradicts the exact-data assumptions; the motion bound, query errors or model must be checked. A clearance certificate with bounded distance-query error replaces exact observations with justified lower bounds and must preserve the assumptions used in minimizing their envelope.

Under the strict convention of adaptive clearance sampling, certification requires the guaranteed lower bound to exceed the requested margin. If it does not, unresolved intervals in adaptive collision checking remain undecided until additional queries or other information resolve them. Failure of this sufficient certificate alone does not establish a collision.