Past exam of the mathematics course of the University of Cambridge / 2004 / iii / Paper 70 / 6

A subdivision surface interrogation interface needs the initial control net, its face/edge/vertex connectivity, the subdivision rule, patch addressing and refinement into child regions that cover the same limit surface. It must supply limit-point evaluation, available tangent/normal data and smoothness information, including the treatment of extraordinary subdivision vertices. A finite refined mesh point is generally not the exact limit point.

For geometric search it must provide certified bounding volumes for each descendant region, bounds that shrink under refinement, and a mesh-to-limit or chord/patch error estimate. With positive convex subdivision masks the active-control convex hull can provide such an enclosure; schemes with negative coefficients need another valid bound. A closed surface also needs consistent orientation, component navigation and containment queries for the enclosed body. The $C^1$ hypothesis supplies first-order tangent information at regular points, not automatically second derivatives or curvature everywhere. These enquiries distinguish an accurate limit-surface algorithm from a calculation only on an approximate control polyhedron.

Interpret the positive-distance assumption as disjoint compact enclosed bodies $A,B$, certified for example by disjoint enclosing volumes. Merely having disjoint drawn control meshes is insufficient if one encloses the other or the meshes do not enclose their limit surfaces. For genuinely disjoint bodies, the closest pair lies on their boundaries: an interior point could move toward the other body and decrease the distance. Thus minimize over all pairs of limit-surface patches.

Use branch and bound on patch pairs. For regions $A_i,B_j$, enclosing bounding volumes give a lower bound $L_{ij}$ on their true minimum distance. For axis-aligned bounding boxes, compute this directly asAny pair of evaluated limit points provides a feasible upper bound; retain the smallest, $U$. Start with a covering list of all coarse patch pairs. At each step, discard a pair when its lower bound is at least $U$, otherwise refine the region with larger bounding diameter/error and enqueue its child pairs. Prefer the pair with smallest lower bound. Update $U$ with new feasible pairs; a local stationary-distance solve can improve it but cannot replace the global search.

Let $L_{\ast }$ be the minimum remaining lower bound, capped by $U$ if the list is empty. The current certificate isStop when $U-L_{\ast }\le \epsilon$. Compactness and shrinking valid patch enclosures ensure convergence to this tolerance under the interface assumptions. An equivalent mesh method must add each mesh's certified limit error; for Hausdorff distance errors $e_A,e_B$, the separation error is at most $e_A+e_B$. Finite mesh distance without such a bound is not the exact minimum distance between subdivision bodies.

First distinguish the ordinary set distance from a signed overlap convention. Ordinary $d(A,B)$ is zero whenever the bodies intersect, and is never negative. Without the positive-separation assumption, test boundary intersections using the subdivision search, and test containment when the boundaries are disjoint. In particular, concentric spheres of unequal radii have positive boundary separation but overlapping enclosed bodies. Include every connected component in the containment tests.

For a meaningful negative result choose translational penetration depth, with orientation fixed:Define signed separation as ordinary positive distance for disjoint bodies, zero at contact, and $-\delta$ when their interiors overlap. This is explicit; the source does not specify which penetration convention its word “distance” intends. Simply negating the closest-boundary distance fails when boundaries cross, because that distance is already zero despite genuine interior overlap.

One implementable extension searches translation space. Obtain an initial separating translation by moving $A$ beyond $B$ along a coordinate direction, using the bodies' enclosing boxes; its norm is an upper bound $U_t$ on $\delta$. Cover a translation box containing the radius-$U_t$ ball, subdividing it into cells. Each cell has a lower bound on $\Vert t\Vert$, given by its box distance from the origin. At a sampled translation, perform certified boundary-intersection and containment queries. A nonoverlapping sample improves $U_t$.

To discard a whole colliding cell, certify an interior witness: if $x$ lies inside $B$ and $x-t_0$ lies inside $A$ with inward clearance $r$, then every translation with $\Vert t-t_0\Vert <r$ still overlaps. Boundary-distance and inside tests establish this certificate. Conversely, a separated sample with clearance $c$ remains separated under translations of norm less than $c$ away from it, by the triangle inequality. For a wholly free cell, use its point nearest the origin as a feasible translation, attaining its cell-norm lower bound. Refine cells whose status is uncertain and whose minimum norm is below $U_t$; discard certified-colliding cells and irrelevant farther cells. Keep the minimum cell-norm bound among cells that might contain a separating translation as $L_t$. Stop when $U_t-L_t\le \epsilon$, reportingRefinement/inside certificates can be implemented from the same surface hierarchy with conservative geometric bounds. Exact contact may require further refinement to decide topology; at finite numerical tolerance report a contact/uncertainty interval instead of inferring overlap from intersecting boxes. This handles crossing and containment and searches for the smallest separating translation, rather than an arbitrary visible intersection depth.