Using implicit equations of parametric curves and surfaces without computing them: Polynomial algebra by values

The availability of the implicit equation of a plane curve or of a 3D surface can be very useful in order to solve many geometric problems involving the considered curve or surface: for example, when dealing with the point position problem or answering intersection questions. On the other hand, it is well known that in most cases, even for moderate degrees, the implicit equation is either difficult to compute or, if computed, the high degree and the big size of the coefficients makes extremely difficult its use in practice.We will show that, for several problems involving plane curves, 3D surfaces and some of their constructions (for example, offsets), it is possible to use the implicit equation (or, more precisely, its properties) without needing to explicitly determine it. We replace the computation of the implicit equation with the evaluation of the considered parameterizations in a set of points. We then translate the geometric problem in hand, into one or several generalized eigenvalue problems on matrix pencils (depending again on several evaluations of the considered parameterizations).This is the so-called “polynomial algebra by values” approach where the huge polynomial equations coming from Elimination Theory (e.g., using resultants) are replaced by big structured and sparse numerical matrices. For these matrices there are well-known numerical techniques allowing to provide the results we need to answer the geometric questions on the considered curves and surfaces.

► Geometric operations are done from Lagrange interpolation data.
► Roots of matrix polynomial determinants are obtained as generalized eigenvalues.
► Accurate computation of offset curves topology.