4.1 Introduction

We have seen in Chap. 1 that curves and surfaces in CAD/CAM systems are usually represented by piecewise polynomial equations of various types. As we will see in the remaining chapters of this book, the governing equations for general interrogation problems on such curve and surface representations (intersections, distance functions, curvature extrema, etc.) reduce to solving systems of nonlinear polynomial equations as follows:

where consists of functions , , each of which is a polynomial in the independent variables , .

Frequently such systems also include square roots of polynomials, which arise from normalization of the normal vector and analytical expressions of the principal curvatures of a surface (see (2.24), (3.3), (3.49), (3.50)).

Example 4.1.1. As an illustrative example, let us consider a simple intersection problem of two planar implicit polynomial (algebraic) curves. Consider two circles and intersecting as shown in Fig. 4.1. In this case , and if we set and , the system of equations becomes

The roots can be obtained by eliminating , and solving for , which gives

Figure 4.1: Intersection of two circles

In this example the degree of the polynomials and the number of variables were low, so we could solve the system by elementary analytical (elimination) calculations. However, most problems that arise in CAD/CAM interrogation have higher degrees and number of variables. Such systems of equations have been solved in earlier approaches by local numerical techniques such as Newton-type methods which require good initial approximation to all roots [69,126], and hence cannot provide full assurance that all roots will be found. On the other hand global techniques find all the roots without initial approximation. We will briefly introduce Newton's method in Sect. 4.2, and the rest of Chap. 4 will be spent on global techniques as well as robustness issues.