Past exam of the mathematics course of the University of Cambridge / 2005 / iii / Paper 66 / 2

Put $U=B_0-A_0$, $T=D_0-C_0$, $D=A_0-C_0$ and $v=V-W$. A point on each moving segment has the form $A_0+sU+tV$ and $C_0+rT+tW$, with $s,r\in [0,1]$. Contact is therefore equivalent toThe contact time of translating line segments is the minimum feasible $t$. This reduces the entire continuous-motion problem to three linear equations and linear inequalities.

In three-dimensional space form the matrix $H=[U,-T,v]$. If it is nonsingular, solveusing a stable linear solver. A candidate with $s,r$ in the unit interval and $t\ge 0$ is the only contact event and hence the earliest one; otherwise no contact occurs. Check initial intersection explicitly, so an already touching pair returns time zero.

If $H$ is singular, use a rank-revealing factorization to test consistency. Write every solution as $x=x_0+Nz$, with columns of $N$ spanning the null space, and minimize its time coordinate subject to the box and nonnegative-time constraints. This is a small linear programming problem. It handles parallel segments, collinear overlap, a continuum of contact times and segments degenerated to points. Infeasibility means no future contact. When $v=0$, the relative geometry is stationary: initially disjoint segments never meet. The first contact is the least feasible nonnegative time, not just an intersection of the two supporting lines.

The same relative coordinates give the proximity time of translating line segments asThis is a convex norm-constrained problem, rather than the linear feasibility problem for contact. One can solve it as a small second-order cone problem. If the distance between the initial line segments is at most $d$, the answer is zero; if no feasible point exists, the threshold is never reached.

For an elementary analytic algorithm, consider the nine combinations in which each of $s,r$ is either free, fixed at zero or fixed at one. In each case, minimize the squared distance over the free parameters. Writing $q(t)$ for $D+tv$ plus the fixed endpoint contributions, and $K$ for the columns belonging to free parameters, stationarity isIf the Gram matrix $K^{T}K$ is nonsingular, $z(t)=-(K^{T}K{)}^{-1}{K}^{T}q(t)$ is affine in time. Retain only the time interval on which its entries lie in $[0,1]$. The residual is then $r_0+t{r}_1$, and feasibility reduces toIntersect its solution interval with $t\ge 0$ and the free-parameter validity interval, and record the first point. Include the four endpoint–endpoint cases, where there are no unfixed segment parameters. Take the earliest valid candidate among all cases. The actual closest pair belongs to one of these faces of the parameter square, so this enumeration cannot miss the first approach.

The complications are the quadratic threshold equation, changes of the active closest-point feature and singular Gram matrices for parallel or degenerate segments. In a singular case, keep the affine family of minimizers and its feasibility bounds, or use the original convex problem; a pseudoinverse answer alone can fall outside the segment even when another minimizer is feasible. Constant-distance cases and tangential threshold contact must also be retained. Merely checking moving endpoints misses approaches between interior points.