We propose a new algorithm to compute the topology of a real algebraic space curve . The novelties of this algorithm are a new technique to achieve the lifting step which recovers points of the space curve in each plane fiber from several projections and a weaker notion of generic position. As distinct to previous work, our sweep generic position does not require that x -critical points have different x -coordinates. The complexity of achieving this sweep generic position property is thus no longer a bottleneck in term of complexity. The bit complexity of our algorithm is O ˜ ( d 18 + d 17 τ ) where d and τ bound the degree and the bitsize of the integer coefficients, respectively, of the defining polynomials of the curve and polylogarithmic factors are ignored. To the best of our knowledge, this improves upon the best currently known results at least by a factor of d 2 .

We address the problem of computing a drawing of high resolution of a plane curve defined by a bivariate polynomial equation P(x,y)=0. Given a grid of fixed resolution, a drawing is a subset of pixels. Our goal is to compute an approximate drawing that (i) contains all the parts of the curve that intersect the pixel edges, (ii) excludes a pixel when the evaluation of P with interval arithmetic on each of its four edges is far from zero.

We address the problem of computing a linear separating form of a system of two bivariate polynomials with integer coefficients, that is a linear combination of the variables that takes different values when evaluated at the distinct solutions of the system. The computation of such linear forms is at the core of most algorithms that solve algebraic systems by computing rational parameterizations of the solutions and this is the bottleneck of these algorithms in terms of worst-case bit complexity. We present for this problem a new algorithm of worst-case bit complexity ÕB(d7 + d6τ) where d and τ denote respectively the maximum degree and bitsize of the input (and where Õ refers to the complexity where polylogarithmic factors are omitted and OB refers to the bit complexity). This algorithm simplifies and decreases by a factor d the worst-case bit complexity presented for this problem by Bouzidi et al. [5]. This algorithm also yields, for this problem, a probabilistic Las-Vegas algorithm of expected bit complexity ÕB(d5 + d4τ).

We address the problem of solving systems of two bivariate polynomials of total degree at most d with integer coefficients of maximum bitsize τ We suppose known a linear separating form (that is a linear combination of the variables that takes different values at distinct solutions of the system) and focus on the computation of a Rational Univariate Representation (RUR).

We present an algorithm for computing a separating linear form of a system of bivariate polynomials with integer coefficients, that is a linear combination of the variables that takes different values when evaluated at distinct (complex) solutions of the system. In other words, a separating linear form defines a shear of the coordinate system that sends the algebraic system in generic position, in the sense that no two distinct solutions are vertically aligned. The computation of such linear forms is at the core of most algorithms that solve algebraic systems by computing rational parameterizations of the solutions and, moreover, the computation of a separating linear form is the bottleneck of these algorithms, in terms of worst-case bit complexity.

We revisit the problem of computing the topology and geometry of a real algebraic plane curve. The topology is of prime interest but geometric information, such as the position of singular and critical points, is also relevant. A challenge is to compute efficiently this information for the given coordinate system even if the curve is not in generic position.

Surfaces of R 3 are ubiquitous in science and engineering, and estimating the local differential properties of a surface discretized as a point cloud or a triangle mesh is a central building block in computer graphics, computer aided design, computational geometry, and computer vision. One strategy to perform such an estimation consists of resorting to polynomial fitting, either interpolation or approximation, but this route is difficult for several reasons: choice of the coordinate system, numerical handling of the fitting problem, and extraction of the differential properties. This article presents a generic C++ software package solving these problems. On the theoretical side and as established in a companion paper, the interpolation and approximation methods provided achieve the best asymptotic error bounds known to date. On the implementation side and following state-of-the-art coding rules in computational geometry, genericity of the package is achieved thanks to four template classes accounting for, (a) the type of the input points, (b) the internal geometric computations, (c) a conversion mechanism between these two geometries, and (d) the linear algebra operations. An instantiation within the Computational Geometry Algorithms Library (CGAL, version 3.3) and using LAPACK is also provided.

This paper addresses the pointwise estimation of differential properties of a smooth manifold S -a curve in the plane or a surface in 3D- assuming a point cloud sampled over S is provided. The method consists of fitting the local representation of the manifold using a jet, by either interpolating or approximating. A jet is a truncated Taylor expansion, and the incentive for using jets is that they encode all local geometric quantities - such as normal or curvatures. On the way to using jets, the question of estimating differential properties is recasted into the more general framework of multivariate interpolation/approximation, a well-studied problem in numerical analysis. On a theoretical perspective, we prove several convergence results when the samples get denser. For curves and surfaces, these results involve asymptotic estimates with convergence rates depending upon the degree of the jet used. For the particular case of curves, an error bound is also derived. To the best of our knowledge, these results are among the first ones providing accurate estimates for differential quantities of order three and more. On the algorithmic side, we solve the interpolation/approximation problem using Vandermonde systems. Experimental results for surfaces of R3 are reported. These experiments illustrate the asymptotic convergence results, but also the robustness of the methods on general Computer Graphics models.