7.1 Introduction

The computation of maximal and minimal distance between point sets in Euclidean space is a basic problem in computational geometry and geometric modeling. It is useful in surface intersections [210], numerical control machining, tolerance region and access space representation in solid modeling, robotics, inspection of manufactured objects [353,297,186,3], and in feature recognition through the construction of medial axis transforms [298,81,450]. For this purpose, it is important to have computational methods which are efficient and reliable to compute extrema for the distance between two variable points where each of those variable points assumes all possible positions in a given set. In practical situations, this set can be a surface, a curve, or a single point.

In this chapter, we examine the computation of the stationary points of the squared distance function in five cases [461]:

1. Between a given point and a variable point on a 3-D space parametric curve.

2. Between a given point and a variable point on a parametric surface patch.

3. Between two variable points located on two given 3-D space parametric curves.

4. Between two variable points, one of which is located on a 3-D space parametric curve and the other is located on a parametric surface patch.

5. Between two variable points, located on two different given parametric surface patches.

We assume that the given curves and surfaces are rational polynomial parametric. However, the methods can be extended to the cases where the given curves and surfaces are represented by implicit polynomials using Lagrange multiplier methods (see Sects. 5.4.1 and 8.4). If the parametric curves and surfaces are in integral/rational B-spline form, the first step is to subdivide the integral/rational B-spline curve or surface patch into a number of integral/rational Bézier curves or patches. The problem thus becomes computing the distances between two point sets, which can be a space point, a integral/rational Bézier curve or a integral/rational Bézier surface patch. The squared distance functions expressed in Bernstein form are developed here for such point sets. This development is based on direct addition and multiplication of two Bernstein forms [106,315] (see Sect. 1.3.2).