Section: New Results

Algebraic Algorithms for Geometric Computing

An Algebraic Approach to Continuous Collision Detection for Ellipsoids

Participant : Bernard Mourrain.

In [28] , we present algebraic conditions for characterizing three configurations of two ellipsoids in R3 that are the most relevant to collision detection: separation, external touching and overlapping. These conditions are given in terms of explicit formulae expressed by the subresultant sequence of the characteristic polynomial of the two ellipsoids and its derivative. For any two ellipsoids, the signs of these formulae can easily be evaluated to classify their configuration. Furthermore, based on these algebraic conditions, an efficient method is developed for continuous collision detection for two moving ellipsoids under arbitrary motion.

This is a joint work with Xiaohong Jia, Yi-King Choi and Wenping Wang from the university of Hong Kong.

On Continued Fraction Expansion of Real Roots of Polynomial Systems, Complexity and Condition Numbers

Participants : Angelos Mantzaflaris, Bernard Mourrain.

In [29] , we elaborate on a correspondence between the coeffcients of a multivariate polynomial represented in the Bernstein basis and in a tensor-monomial basis, which leads to homography representations of polynomial functions, that use only integer arithmetic (in contrast to Bernstein basis) and are feasible over unbounded regions. Then, we study an algorithm to split this representation and we obtain a subdivision scheme for the domain of multivariate polynomial functions. This implies a new algorithm for real root isolation, MCF, that generalizes the Continued Fraction (CF) algorithm of univariate polynomials. A partial extension of Vincent's Theorem for multivariate polynomials is presented, which allows us to prove the termination of the algorithm. Bounding functions, projection and preconditioning are employed to speed up the scheme. The resulting isolation boxes have optimized rational coordinates, corresponding to the first terms of the continued fraction expansion of the real roots. Finally, we present new complexity bounds for a simplified version of the algorithm in the bit complexity model, and also bounds in the real RAM model for a family of subdivision algorithms in terms of the real condition number of the system. Examples computed with our C++ implementation illustrate the practical aspects of our method.

This is a joint work with E. Tsigaridas, from the Department of Computer Science, University of Aarhus.

Matrix-based representations of rational hypersurfaces

Participants : Laurent Busé, Nicolas Botbol.

This ongoing work is related to matrix-based representations of rational hypersurfaces whose theoretical fundations has been recently developed by our team and several other authors in the context of the implicitization problem. Being given a parameterized curve or hypersurface, this method consists in building a matrix whose entries are typically linear forms in the variables of the ambient space and such that the ideal generated by the maximal minors of this matrix provide a good approximation of the original curve or hypersurface.

We aim to study and determine the geometric informations that are contained in a representation matrix. In particular, we are currently adressing the two following questions :

1) understand the extraneous components that are added by taking the initial Fitting ideal of a representation matrix, with respect to the original curve or surface. Indeed, these extraneous components appear because of the good behavior of Fitting ideals under change of bases. Therefore, one can expect that these extraneous components yields some geometric properties of a curve or surface as a member of a certain family. 2) examine the extraction of singularities from a representation matrix, similarly to the recent results on what is called "singular factors" for the case of rational curves.

The surface/surface intersection problem by means of matrix based representations

Participants : Laurent Busé, Thang Luu Ba.

Evaluating the intersection of two rational parameterized algebraic surfaces is an important problem in solid modeling. In this work, we made use of some generalized matrix based representations of parameterized surfaces in order to represent the intersection curve of two such surfaces as the zero set of a matrix determinant. As a consequence, we extended to a dramatically larger class of rational parameterized surfaces the applicability of a general approach to the surface/surface intersection problem due to J. Canny and D. Manocha. In this way, we obtained compact and efficient representations of intersection curves allowing to reduce some geometric operations on such curves to matrix operations using results from linear algebra.

See the preprint version at http://hal.inria.fr/inria-00620947/en/