Abstract: Algebraic operations on sets of complex numbers produce remarkably rich geometrical structures, with diverse applications and connections to science and engineering. For "simple" operands, such as circular disks, precise descriptions of their algebraic combinations are available in terms of the Cartesian and Cassini ovals, and higher-order generalizations. Algorithms can be formulated to approximate algebraic operations on complex sets with general (piecewise-smooth) boundaries to a given precision. This "Minkowski algebra of complex sets" is the natural generalization of (real) interval arithmetic to sets of complex numbers. It provides a versatile two-dimensional "shape operator" language, with connections to mathematical morphology, geometrical optics, and stability analysis of dynamic systems.
Abstract: Camera pose estimation is the problem of determining the position and orientation of an internally calibrated camera from known 3D reference points and their images. We briefly survey several existing methods for pose estimation, then introduce our new complete linear method, which is based on a symbolic-numeric method from the geometric (Jet) theory of partial differential equations. The new method is stable and robust. In particular, it can deal with the points near critical configurations. Numerical experiments are given to show the performance of the new method.
Abstract: Given an irreducible polynomial in two or more variable with complex floating point coefficients we find a lower bound on its distance to a reducible polynomial of the same degrees. This is accomplished by using generalizations of an irreducibility test of Ruppert together with theory of bounding matrices away from those with lower ranks which involves singular value decompositions, and psuedo-inverses. We compare a couple different ways of computing these bounds.
Abstract: We present a new method for constructing a low degree C1 implicit spline representation of a given parametric planar curve. To ensure the low degree condition, quadratic B-splines are used to approximate the given curve via orthogonal projection in Sobolev spaces. Adaptive knot removal, which is based on spline wavelets, is used to reduce the number of segments. The B-spline segments are implicitized. After multiplying the implicit B--spline segments by suitable polynomial factors the resulting bivariate functions are joined along suitable transversal lines. This yields to a globally C1 bivariate function. Some applications of the proposed method is presented.
Abstract: We consider the problem of interpolating a multivariate polynomial that is given as a black box. When the target polynomial is sparse, there are efficient algorithms taking advantage of this situation, such as Zippel's probabilistic algorithm and the Ben-Or/Tiwari algorithm. These methods are developed for exact arithmetic environments. Interestingly, the method of Ben-Or and Tiwari is similar to that of Prony's from 1795 for interpolating a sum of exponential functions. Recent work by Golub, Milanfar, and Varah recasting Prony's method as a generalized eigenvalue problem may provide the key to a numerically sound symbolic-numeric sparse polynomial interpolation. This method avoids explicitly constructing and solving the generating polynomial in the interpolation process. Furthermore, in the finite precision arithmetic, evaluating the black box at appropriate primitive roots of unity may not only improve the condition embedded in the interpolation steps, but also provide a numeric method for recovering all variables at once in the target polynomial. In addition to the standard power basis, our approach can be applied to polynomials represented in some non-standard bases. We discuss general issues and a framework for sparse, black-box, approximate polynomial interpolation, our algorithm for solving this problem, and details of our numerical experiments.
Abstract: This talk presents a new symbolic-numeric method for computing self-intersection of surface with arbitrary rational parameterization. The problem of finding surface self-intersection can be stated as a problem of solving system of non-linear algebraic equations (for surface with rational parameterization). Symbolic part of this method uses Groebner bases method for solving given system of non-linear algebraic equations which can be easily replaced by resultant method. Any of these elimination methods gives on the output one-dimensional algebraic set represented by the polynomial P(u,v) = 0. Every algebraic set of this type consist of open and closed components. The algorithm computes start points on all components which correspond to surface self-intersection. Then component splitting is used to partition the domain such that each resulting region contains only one component. Finally, tracing is used to evaluate the curve on the given region and to obtain appropriate part of the surface self-intersection. The technique to handle singularities is also presented. The algorithm has been implemented in MathWorks Matlab 6.1 and CoCoA 4.2 is used for reduced Groebner basis computations.
Abstract: We propose the use of various tools from algebraic geometry, with an emphasis on toric (or sparse) elimination theory, in order to predict the support of the implicit equation of a parametric hypersurface. The problem of implicitization lies at the heart of several algorithms in geometric modeling and computer-aided design. In the case of two specific implicitization algorithms IPSOS results in tremendous efficiency improvements. Other implicitization methods shall probably be able to benefit from our work. More specifically, we use information on the support of the toric resultant, and degree bounds, formulated in terms of the mixed volume of Newton polytopes. The computed support of the implicit equation depends on the sparseness of the parametric expressions and is much tighter than the one predicted by degree arguments. Our Maple implementation illustrates many examples in which we always obtain the exact support.
Abstract: Given a set of nodal points which define a polygonal geometry, such as the vertices of a convex or concave polygon, a smooth and bounded test function can be constructed in explicit algebraic form. It smoothly distributes the given values at the nodes over the interior of the domain. The closed form representation is constructed by combining simple geometric descriptions, such as boundary edge length and area. The smooth test function on a convex polygon can be constructed as the rational combination of the product of areas. Accordingly the representation is rational polynomial. The test function on a concave or multiply-connected polygon is constructed as the function of areas and edge lengths. Accordingly, a square root term enters the representation. Computer algebra is a uniquely suited for developing such test functions which satisfy required geometric conditions exactly, such as boundary conditions, and approximates unknown behavior reasonably, such as domain behavior. A method for constructing linear edged test functions satisfying constant and linear field conditions will be presented.
Abstract: A few years ago S-H Kim investigated some problems at the boundary of number theory, optimization, and geometry. One question regarded an optimal packing of certain "triangular oval" planar curves and another looked at some related transformations of R^2 to R^2. While these were cast using trigonometric functions in a calculus setting, it turns out that a tool from computational polynomial algebra, Groebner bases, may be used to advantage. The goal is to convey some sense of where and how computational technology can be of use in approaching and illustrating the theory behind that work.