We present an efficient, globally G 1 –continuous scheme for extracting Bézier patches from any mesh with valence-four vertices and polygonal faces, that is, the mesh topology that arises in Doo-Sabin subdivision. The Bézier points are given explicitly as local, weighted averages in the vicinity of each vertex of the mesh, yielding bi-quadratic patches in regular regions and bi-quartic or bi-quintic patches in the vicinity of irregular regions. In particular, we first derive simple bi-quadratic averaging masks that produce quadratic patches that join with C 1 continuity in regular regions. In the vicinity of irregular faces, we elevate the degree, then impose certain symmetric gluing data of degree two on the patch interfaces, and compute explicitly masks as solution of the G 1 constraints. The resulting scheme, named G 1 ADS, ensures machine precision adherence to the G 1 conditions, reproduces quadratic C 1 B-splines at the regular regions, and enjoys a minimal number of degree elevated patches in the vicinity of irregular regions. We evaluate the performance of G 1 ADS quantitatively and qualitatively on several challenging benchmarks, in terms of accuracy, curvature and isophote analysis, and we compare with the state-of-the-art method. Our results demonstrate that G 1 ADS is efficient, robust and more accurate, producing high quality surfaces that converge to the respective Doo-Sabin limit surface.

We present a new algorithm for computing the real radical of an ideal I and, more generally, the S-radical of I, which is based on convex moment optimization. A truncated positive generic linear functional σ vanishing on the generators of I is computed solving a Moment Optimization Problem (MOP). We show that, for a large enough degree of truncation, the annihilator of σ generates the real radical of I. We give an effective, general stopping criterion on the degree to detect when the prime ideals lying over the annihilator are real and compute the real radical as the intersection of real prime ideals lying over I.

In this paper we provide a new method to certify that a nearby polynomial system has a singular isolated root and we compute its multiplicity structure. More precisely, given a polynomial system f = (f1, ..., fN) ∈ C[x1, ..., xn]N, we present a Newton iteration on an extended deflated system that locally converges, under regularity conditions, to a small deformation of f such that this deformed system has an exact singular root. The iteration simultaneously converges to the coordinates of the singular root and the coefficients of the so-called inverse system that describes the multiplicity structure at the root. We use α-theory test to certify the quadratic convergence, and to give bounds on the size of the deformation and on the approximation error. The approach relies on an analysis of the punctual Hilbert scheme, for which we provide a new description. We show in particular that some of its strata can be rationally parametrized and exploit these parametrizations in the certification. We show in numerical experimentation how the approximate inverse system can be computed as a starting point of the Newton iterations and the fast numerical convergence to the singular root with its multiplicity structure, certified by our criteria.

Arrangements of geometric objects refer to the spatial partitions formed by the objects, and they serve as an underlining structure of motion design, analysis, and planning in CAD/CAM, robotics, molecular modeling, manufacturing, and computer-assisted radio-surgery. Arrangements are especially useful to collision detection, which is a key task in various applications such as computer animation, virtual reality, computer games, robotics, CAD/CAM, and computational physics. Ellipsoids are commonly used as bounding volumes in approximating complex geometric objects in collision detection. In this article, we present an in-depth study on the arrangements formed by two ellipsoids. Specifically, we present a classification of these arrangements and propose an efficient algorithm for determining the arrangement formed by any particular pair of ellipsoids. A stratification diagram is also established to show the connections among all the arrangements formed by two ellipsoids. Our results, for the first time, elucidate all possible relative positions between two arbitrary ellipsoids and provide an efficient and robust algorithm for determining the relative position of any two given ellipsoids, therefore providing the necessary foundation for developing practical and trustworthy methods for processing ellipsoids for collision analysis or simulation in various applications.

Given a multi-index sequence σ, we present a new efficient algorithm to compute generators of the linear recurrence relations between the terms of σ. We transform this problem into an algebraic one, by identifying multi-index sequences, multivariate formal power series and linear functionals on the ring of multivariate polynomials. In this setting, the recurrence relations are the elements of the kernel Iσ of the Hankel operator Hσ associated to σ. We describe the correspondence between multi-index sequences with a Hankel operator of finite rank and Artinian Gorenstein Algebras. We show how the algebraic structure of the Artinian Gorenstein algebra Aσ associated to the sequence σ yields the structure of the terms σ α for all α ∈ Nn. This structure is explicitly given by a border basis of Aσ, which is presented as a quotient of the polynomial ring K [x1, ..., xn] by the kernel Iσ of the Hankel operator Hσ. The algorithm provides generators of Iσ constituting a border basis, pairwise orthogonal bases of Aσ and the tables of multiplication by the variables in these bases. It is an extension of Berlekamp-Massey-Sakata (BMS) algorithm, with improved complexity bounds. We present applications of the method to different problems such as the decomposition of functions into weighted sums of exponential functions, sparse interpolation, fast decoding of algebraic codes, computing the vanishing ideal of points, and tensor decomposition. Some benchmarks illustrate the practical behavior of the algorithm.

This paper presents two new constructions related to singular solutions of polynomial systems. The first is a new deflation method for an isolated singular root. This con- struction uses a single linear differential form defined from the Jacobian matrix of the input, and defines the deflated system by applying this differential form to the original system. The advantages of this new deflation is that it does not introduce new variables and the increase in the number of equations is linear instead of the quadratic increase of previous methods. The second construction gives the coefficients of the so-called inverse system or dual basis, which defines the multiplicity structure at the singular root. We present a system of equations in the original variables plus a relatively small number of new variables. We show that the roots of this new system include the original singular root but now with multiplicity one, and the new variables uniquely determine the multiplicity structure. Both constructions are 'exact' in that they permit one to treat all conjugate roots simultaneously and can be used in certification procedures for singular roots and their multiplicity structure with respect to an exact rational polynomial system.

We extend the theory and the algorithms of Border Basis to systems of Laurent polynomial equations, defining "toric" roots. Instead of introducing new variables and new relations to saturate by the variable inverses, we propose a more efficient approach which works directly with the variables and their inverse. We show that the commutation relations and the inversion relations characterize toric border bases. We explicitly describe the first syzygy module associated to a toric border basis in terms of these relations. Finally, a new border basis algorithm for Laurent polynomials is described and a proof of its termination is given for zero-dimensional toric ideals.

In this paper, we generalized the construction of border bases to non-zero dimensional ideals for normal forms compatible with the degree, tackling the remaining obstacle for a general application of border basis methods. First, we give conditions to have a border basis up to a given degree. Next, we describe a new stopping criteria to determine when the reduction with respect to the leading terms is a normal form. This test based on the persistence and regularity theorems of Gotzmann yields a new algorithm for computing a border basis of any ideal, which proceeds incrementally degree by degree until its regularity. We detail it, prove its correctness, present its implementation and report some experimentations which illustrate its practical good behavior.

In isogeometric anlaysis, parameterization of computational domain has great effects as mesh generation in finite element analysis. In this paper, based on the concept of harmonic map from the computational domain to parametric domain, a variational approach is proposed to construct the parameterization of computational domain for 2D isogeometric analysis. Different from the previous elliptic mesh generation method in finite element analysis, the proposed method focus on isogeometric version, and converts the elliptic PDE into a nonlinear optimization problem. A regular term is integrated into the optimization formulation to achieve more uniform grid near convex(concave) parts of the boundary. Several examples are presented to show the efficiency of the proposed method.

In the paper, we address the important problem of tensor decomposition which can be seen as a generalisation of Singular Value Decomposition for matrices. We consider general multilinear and multihomogeneous tensors. We show how to reduce the problem to a truncated moment matrix problem and we give a new criterion for flat extension of Quasi-Hankel matrices. We connect this criterion to the commutation characterisation of border bases. A new algorithm is described: it applies for general multihomogeneous tensors, extending the approach of J.J. Sylvester on binary forms. An example illustrates the algebraic operations involved in this approach and how the decomposition can be recovered from eigenvector computation.

We develop a new symbolic-numeric algorithm for the certification of singular isolated points, using their associated local ring structure and certified numerical computations. An improvement of an existing method to compute inverse systems is presented, which avoids redundant computation and reduces the size of the intermediate linear systems to solve. We derive a one-step deflation technique, from the description of the multiplicity structure in terms of differentials. The deflated system can be used in Newton-based iterative schemes with quadratic convergence. Starting from a polynomial system and a sufficiently small neighborhood, we obtain a criterion for the existence and uniqueness of a singular root of a given multiplicity structure, applying a well-chosen symbolic perturbation. Standard verification methods, based e.g. on interval arithmetic and a fixed point theorem, are employed to certify that there exists a unique perturbed system with a singular root in the domain. Applications to topological degree computation and to the analysis of real branches of an implicit curve illustrate the method.

In this paper we derive aggregate separation bounds, named after Davenport-Mahler-Mignotte (DMM), on the isolated roots of polynomial systems, specifically on the minimum distance between any two such roots. The bounds exploit the structure of the system and the height of the sparse (or toric) resultant by means of mixed volume, as well as recent advances on aggregate root bounds for univariate polynomials, and are applicable to arbitrary positive dimensional systems. We improve upon Canny's gap theorem [7] by a factor of O(dn-1), where d bounds the degree of the polynomials, and n is the number of variables. One application is to the bitsize of the eigenvalues and eigenvectors of an integer matrix, which also yields a new proof that the problem is polynomial. We also compare against recent lower bounds on the absolute value of the root coordinates by Brownawell and Yap [5], obtained under the hypothesis there is a 0-dimensional projection. Our bounds are in general comparable, but exploit sparseness; they are also tighter when bounding the value of a positive polynomial over the simplex. For this problem, we also improve upon the bounds in [2, 16]. Our analysis provides a precise asymptotic upper bound on the number of steps that subdivision-based algorithms perform in order to isolate all real roots of a polynomial system. This leads to the first complexity bound of Milne's algorithm [22] in 2D.

This paper presents a reconstruction pipeline for recovering branching structure of trees from laser scanned data points. The process is made up of two main blocks: segmentation and reconstruction. Based on a variational k-means clustering algorithm, cylindrical components and ramified regions of data points are identified and located. An adjacency graph is then built from neighborhood information of components. Simple heuristics allow us to extract a skeleton structure and identify branches from the graph. Finally, a B-spline model is computed to give a compact and accurate reconstruction of the branching system.

An algorithm is presented for the computation of the topology of a non-reduced space curve defined as the intersection of two implicit algebraic surfaces.

Let f1,..., fs be a system of polynomials in K[x1,..., xm] generating a zero-dimensional ideal I , where K is an arbitrary algebraically closed field. Assume that the factor algebra A = K[x1 , . . . , xm]/I is Gorenstein and that we have a bound delta > 0 such that a basis for A can be computed from multiples of f1,..., fs of degrees at most delta. We propose a method using Sylvester or Macaulay type resultant matrices of f1,..., fs and J , where J is a polynomial of degree delta generalizing the Jacobian, to compute moment matrices, and in particular matrices of traces for A. These matrices of traces in turn allow us to compute a system of multiplication matrices {Mxi|i = 1,..., m} of the radical of I, following the approach in the previous work by Janovitz-Freireich, Ronyai and Szanto. Additionally, we give bounds for delta for the case when I has finitely many projective roots.

We describe a new algorithm for the visualisation of implicit algebraic curves, which isolates the singular points, compute the topological degree around these points in order to check that the topology of the curve can be deduced from the points on the boundary of these singular regions. The other regions are divided into x or y regular regions, in which the branches of the curve are also determined from information on the boundary. Combined with enveloping techniques of the polynomial represented in the Bernstein basis, it is shown on examples that this algorithm is able to render curves defined by high degree polynomials with large coefficients, to identify regions of interest and to zoom safely on these regions.

We overview a new method for computing the arrangement of semi-algebraic curves. A subdivision approach is used to compute the topology of the algebraic objects and to segment the boundary of regions defined by these objects. An efficient insertion technique is described, which detects regions in conflict and updates the underlying arrangement structure. We describe the general framework of this method, the main region insertion operation and the specializations of the key ingredients for the different types of objects: implicit, parametric or piecewise linear curves.

Blind identification of under-determined mixtures (UDM) is involved in numerous applications, including multi-way factor analysis (MWA) and signal processing. In the latter case, the use of high-order statistics (HOS) like cumulants leads to the decomposition of symmetric tensors. Yet, little has been published about rank-revealing decompositions of symmetric tensors. Definitions of rank are discussed, and useful results on generic rank are proved, with the help of tools borrowed from algebraic geometry

This paper describes a new method for computing the normal form of a polynomial modulo a zero-dimensional ideal I. We give a detailed description of the algorithm, a proof of its correctness, and finally experimentations on classical benchmark polynomial systems. The method that we propose can be thought as an extension of both the Gröbner basis method and the Macaulay construction. We have weaken the monomial ordering requirement for bases computations, which allows us to construct new type of representations for the quotient algebra. This approach yields more freedom in the linear algebra steps involved, which allows us to take into account numerical criteria while performing the symbolic steps. This is a new feature for a symbolic algorithm, which has a huge impact on the practical efficiency.

International audience

We propose new Las Vegas randomized algorithms for the solution of a square nondegenerate system of equations, with well-separated roots. The algorithms use $\Oc (\delta\, \csttn D^{2} \log(D) \log(b))$ arithmetic operations (in addition to the operations required to compute the normal form of the boundary monomials modulo the ideal) to approximate all real roots of the system as well as all roots lying in a fixed n-dimensional box or disc. Here D is an upper bound on the number of all complex roots of the system (e.g., Bezout or Bernshtein bound), $\delta$ is the number of real roots or the roots lying in the box or disc, and $\epsilon=2^{-b}$ is the required upper bound on the output errors. For computing the normal form modulo the ideal, the efficient practical algorithms of [B. Mourrain and P. Trébuchet, in Proceedings of the International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2000, pp. 231--238] or [J. C. Faugère, J. Pure Appl. Algebra, 139 (1999), pp. 61--88] can be applied. We also yield the bound $\Oc( \csttn D^{2} \log(D) )$ on the complexity of counting the numbers of all roots in a fixed box (disc) and all real roots. For a large class of inputs and typically in practical computations, the factor $\delta$ is much smaller than $D, \delta=o(D)$. This improves by the order of magnitude the known complexity estimates of the order of at least 3 n D 4 + D 3 log(b) or D 4 , which so far are the record estimates even for the approximation of a single root of a system and for each of the cited counting problems, respectively. Our progress relies on proposing several noveltechniques. In particular, we exploit the structure of matrices associated to a given polynomial system and relate it to the associated linear operators, dual space of linear forms, and normal forms of polynomials in the quotient algebra; furthermore, our techniques support the new nontrivial extension of the matrix sign and quadratic inverse power iterations to the case of multivariate polynomial systems, where we emulate the recursive splitting of a univariate polynomial into factors of smaller degree.

This paper focuses on the problem of calibration from a single view and a map of a scene. This situation arises quite often when modelling urban scenes, e.g. for augmented reality purposes. We show how some scenes constraints can be used to achieve a calibration like procedure. An example excerpted from a sequence of pictures for which self-calibration-like techniques consistently fail illustrates some of the benefits of the approach.

The purpose of this paper is to present a new method to design exact geometric predicates in algorithms dealing with curved objects such as circular arcs.We focus on the comparison of the abscissae of two intersection points of circle arcs, which is known to be a difficult predicate involved in the computation of arrangements of circle arcs.We present an algorithm for deciding the x-order of intersections from the signs of the coefficients of a polynomial, obtained by a general approach based on resultants.This method allows the use of efficient arithmetic and filtering techniques leading to fast implementation as shown by the experimental results. I. INTRODUCTIONImplementing geometric algorithms is difficult because the decisions made by such algorithms are taken on the basis of simple geometric questions, called predicates, solved by the evaluation of continuous functions subject to rounding errors, though the algorithms are basically of combinatorial and discrete nature.For example, the sweep line paradigm is a combinatorial algorithm relying on predicates such as x-comparisons.The use of floating point arithmetic to evaluate predicates often produces inconsistencies.For instance, plane sweep algorithms, which are basic tools in computational geometry, are known to be very sensitive to numerical errors: when computing arrangements of curves, a plane sweep algorithm needs to sort intersection points between curves by x coordinates, and if, due to erroneous numerical computations, the x comparison test is not transitive, the algorithm may crash.To cope with this problem, people may either work on the *This research

The silhouette algorithm developed by Canny (1988, 1993) is a general motion planning algorithm which is known to have the best complexity of all of the general and complete algorithms. The authors present a symbolic-numeric version of the algorithm. This version does not require the symbolic computation of the determinants of resultant matrices, and can work on floating point arithmetic. Though its combinatorial complexity remains the same, but its algebraic complexity has been improved significantly which is very important towards its implementation. Several numerical examples are also presented.

In this paper, we present a new method for solving square polynomial systems with no zero at infinity. We analyze its complexity, which indicates substantial improvements, compared with the previously known methods for solving such systems. We describe a framework for symbolic and numeric computations, developed in C++, in which we have implemented this algorithm. We mention the techniques that are involved in order to build efficient codes and compare with existing softwares. We end by some applications of this method, considering in particular an autocalibration problem in Computer Vision and an identification problem in Signal Processing, and report on the results of our first implementation.

In this article, we present a new met.hodfor computing the deconiposition of a variety into irreducible componc:nts.It. is bawd on a property of Bczoutia.nmat.ricc:s; which allows us to c:omput,e a multiple of t.lio Chow form of t.he isolat,cil points of the varict.yand to deduce a rational representation of thcsc points.This t,ools is used recursively to compute t,he irreduc.iblccomponents from the lowest to the highest.dimension.The asymptotic complexity is of the same order t.han the best complesity bound known for this problem.Our approach provides a subst,nntial simplification of the previous methods and yields bounds on the height of polynomials involved in these representations.=\n iml.'lelllrnt.ation in MAPLE of t.his algorithm is described at, thr end.0

For a system of polynomial equations, we seek its specified root, maximizing or minimizing the absolute value of a fixed polynomial over all roots of the system. The latter requirement to a root, complicating the already difficult classical problem, is motivated by several practical applications. We first reduce the solution to the computation of the eigenvector of an associated matrix. Our novel treatment of this rather customary stage enables us to unify several known approaches and to simplify substantially the solution of an overconstrained polynomial system having only a simple root or a few roots. Likewise, when the reduction of a general polynomial system to an eigenproblem relies on the Gröbner basis techniques, we also obtain substantial simplification. Then we elaborate application of the power method and the (shifted) inverse power method to the solution of the resulting eigenproblem. Our elaboration is not straight-forward since we achieve the computation preserving the sparsity and the structure of the associated matrix involved. This enables the decrease of the arithmetic cost by roughly factor N , denoting the dimension of the associated resultant matrix. Furthermore, our experiments show that our computations can be performed numerically, with single or double precision arithmetic, and the iteration converged to the specified root quite fast.

Award 668365) We propose new Las Vegas randomized algorithms for the solution of a multivariate generic or sparse polynomial system of equations. The algorithms use O ( ( +4 n)3 nD2 log b) arithmetic operations to approximate all real roots of the system as well as all roots lying in a fixed n-dimensional box or disc. Here D is an upper bound on the number of all the roots of the system, is the number of real roots or the roots lying in the box or disc, =2;b is the required upper bound on the output errors, and O (s) stands for O(s log c s), c being a constant independent of s. We also yield the bounds O (12 nD2) for the complexity of counting the numbers of all roots in a fixed box (disc) and all real roots and O (12 nD2 log b) for the complete solution of generic system. For a large class

Type II Z/sub 4/-codes are introduced as self-dual codes over the integers modulo 4 containing the all-one vector and with Euclidean weights multiple of 8. Their weight enumerators are characterized by means of invariant theory. A notion of extremality for the Euclidean weight is introduced. Their binary images under the Gray map are formally self-dual with even weights. Extended quadratic residue Z/sub 4/-codes are the main example of this family of codes. They are obtained by Hensel lifting of the classical binary quadratic residue codes. Their binary images have good parameters. With every type II Z/sub 4/-code is associated via construction A modulo 4 an even unimodular lattice (type II lattice). In dimension 32, we construct two unimodular lattices of norm 4 with an automorphism of order 31. One of them is the Barnes-Wall lattice BW32.

We explore the geometric and algebraic relations that exist between correspondences of points and lines in an arbitrary number of images. We propose to use the formalism of the Grassmann-Cayley algebra as the simplest way to make both geometric and algebraic statements in a very synthetic and effective way (i.e. allowing actual computation if needed). We have a fairly complete picture of the situation in the case of points; there are only three types of algebraic relations which are satisfied by the coordinates of the images of a 3-D point: bilinear relations arising when we consider pairs of images among the N and which are the well-known epipolar constraints, trilinear relations arising when we consider triples of images among the N, and quadrilinear relations arising when we consider four-tuples of images among the N. In the case of lines, we show how the traditional perspective projection equation can be suitably generalized and that in the case of three images there exist two independent trilinear relations between the coordinates of the images of a 3-D line.>