Campuses:

<span class=strong>Reception and Poster Session</span>

Tuesday, May 29, 2007 - 4:30pm - 6:30pm
Lind 400
  • Real-time Algebraic Surface Visualization
    Tor Dokken (SINTEF)
    Joint work with Johan Simon Seland.

    We demonstrate a ray tracing type technique for rendering
    algebraic surfaces using
    programmable graphics hardware (GPUs). Our approach allows
    for real-time
    exploration and manipulation of arbitrary real algebraic
    surfaces, with no preprocessing
    step, except that of a possible change of polynomial basis.
    The algorithm is based on the blossoming principle of
    trivariate Bernstein-Bézier
    functions over a tetrahedron. By computing the blossom of
    the function describing the
    surface with respect to each ray, we obtain the
    coefficients of a univariate Bernstein
    polynomial, describing the surface's value along each ray.
    We then use Bézier
    subdivision to find the first root of the curve along each
    ray to display the surface.
    These computations are performed in parallel for all rays
    and executed on a GPU.

    The limiting factor for the maximum degree of surface
    visualization is the number of
    registers available in each fragment pipeline. Our Nvidia
    7800 GPU has 32 four-wide
    temporary registers, in comparison next generation GPUs
    (DX10) are expected to
    have 4096 registers[1], which will allow us to visualize
    surfaces of much higher total
    degree using our current approach.
  • Linkage Problems and Real Algebraic Geometry
    Reinhard Steffens (Johann Wolfgang Goethe-Universität Frankfurt)
    Joint work with Thorsten Theobald.

    Linkages are graphs whose edges are rigid bars, and they arise
    as a natural model in many applications in computational
    geometry,
    molecular biology and robotics. Studying linkages naturally
    leads
    to a variety of questions in real algebraic geometry, such as:

    1. Given a rigid graph with prescribed edge lengths, how
      many
      embeddings are there?

    2. Given a 1-degree-of-freedom linkage, how can one
      characterize
      and compute the trajectory of the vertices?


    From the real algebraic point of view, these questions are
    questions
    of specially-structured real algebraic varieties. On the poster
    we
    exhibit some techniques from sparse elimination theory to
    analyze these problems. In particular, we show that certain
    bounds (e.g. for Henneberg-type graphs) naturally arise from
    mixed volumes and Bernstein's theorem.
  • The Voronoi Circle of Smooth Closed Curves
    Ioannis Emiris (National University of Athens)
    Voronoi diagrams in the plane are fundamental objects in computational
    geometry. We wish to extend their study to nonlinear objects, such as
    ellipses, under the Euclidean distance. From the point of view of
    algebraic complexity, the bottleneck is in computing the Voronoi
    circle of 3 objects. We present a subdivision scheme that
    approximates, to any desired accuracy, the Voronoi circle of 3 smooth
    parametric closed curves. It exploits the underlying geometry to
    achieve quadratic convergence. The algorithm has been implemented and
    experimental results are shown.
  • Arrangements of Real Algebraic Plane Curves
    Michael Kerber (Max-Planck-Institut für Informatik)
    We present a complete and exact algorithm for computing the arrangement of algebraic curve segments, based on the generic sweep-line algorithm from Bentley and Ottmann. We do not impose any condition on the degree or the geometry of the curves defining the arrangement.

    The predicates for the sweep-line algorithm are all reduced to the {em Curve analysis} (compute the topology and critical point locations of one curve) and the {em Curve pair analysis} (compute the geometry of a pair of curves, in particular find their real intersections).

    Only few exact information is precalculated using subresultants and Sturm-Habicht sequences; numerical methods both speed-up the analysis of curves and curve pairs in generic cases, and also find non-generic cases during the analysis. Non-generic positions are transformed to generic ones by a change of coordinates, but a subsequent back-transformation provides the results in the original coordinate system.

    A preliminary version of the algorithm has been implemented in the EXACUS-library AlciX.

    (joint work with Arno Eigenwillig)
  • Linear Precision for Toric Patches
    Luis Garcia-Puente (Texas A & M University)
    We study linear precision for multi-sided parametric patches of any dimension,
    showing that every parametric patch has a unique reparametrization which
    has linear precision and giving a geometric criterion for when this
    reparametrization is rational.
    For toric patches, this geometric criterion is equivalent to a certain toric differential
    defining a birational map.
    While the reparametrization of a general toric patch having linear precision is not
    necesssarily a rational function, it is computed by iterative proportional fitting, a
    numerical algorithm from statistics.
  • Guided Surfaces
    Jörg Peters (University of Florida)
    Guided surface construction separates the conceptual design
    and the
    representation by
    prescribing local shape via guide surfaces and then
    sampling these guides with a finite number of tensor-product
    patches.
    This approach yields C2 subdivision surfaces and
    polynomial C2 surfaces, typically with good curvature
    distribution.
  • An Implicit Equation of a Canal Surface
    Severinas Zube (Vilnius State University)
    The canal surface with spine curve e=(c(t),r(t)) is the envelope
    of one parameter family of spheres centered at c(t) with
    radius r(t). In this poster we present efficient algorithm for
    computing implicit equation and degree of a canal surface with
    rational spine curve.

    By using Laguerre and Lie geometry, we derive that the implicit
    equation of canal surface is related to an implicit equation of a
    dual variety to a curve in 5 dimensional projective space.
    We define a mu-basis for the dual variety to the curve
    and present a simple algorithm for its computation. The mu-basis
    consists of two polynomials p(x,t) and q(x,t) that are linear in x.
    The implicit equation of dual variety is then obtained as the resultant
    of p and q with respect to t.
  • Towards a List of Challenging Visualization Problems in Real Algebraic Geometry
    Oliver Labs (Universität des Saarlandes)
    Recently, the visualization of algebraic implicitly given
    curves and surfaces of degree greater than 3 has become an area of active
    research.
    Most of the approaches either use raytracing or triangulation techniques to
    produce a good approximate picture of the varieties, often by using recent
    hardware equipment such as graphics card processors.

    However, the examples which are used as test-cases for these algorithms
    often do not reflect the most complicated situations which can actually
    occur simply because these examples are not easy to construct or to find in
    the literature.
    Actually, in many cases it is currently even not known what the most
    difficult possible example is.

    We provide a list of equations of which we can prove that
    the examples are at least close to the most difficult possible ones.
    We restrict ourselves to plane curves and surfaces in three-space.
    For convenience, our list is available as a text-file and as a SINGULAR-file.
  • Discriminants and New Real Topological Complexity Bounds
    J. Maurice Rojas (Texas A & M University)
    We present new upper bounds on the topological complexity
    of certain real hypersurfaces defined by sparse polynomials.
    More precisely, given a polynomial f in n variables with n+k
    distinct exponent vectors, we show the following:

    (A) With high probability (with respect to a broad family of
    probability measures we can classify) the positive real
    zero set of f has no more than O(1 +
    (k-1)/(n+1))n+1 connected components.

    (B) For fixed exponent vectors and varying coefficients, the
    number
    smooth diffeotopy types for the (toric) real zero
    set is O(n11),
    assuming k
    All previous bounds for the number of connected components
    (resp.
    smooth diffeotopy types) were exponential in k (resp.
    exponential in n).

    These results are joint with Martin Avendano, Joel Gomez, and
    Andrew Niles.
  • An Algorithm for Lifting Points in a Tropical Variety
    Anders Jensen (Aarhus University)Thomas Markwig (Universität Kaiserslautern)Hannah Markwig (University of Minnesota, Twin Cities)
    One of the basic theorems of tropical geometry states that given a point on a
    tropical variety (defined using initial ideals), there exists a
    Puiseux-valued lift of this point in the algebraic variety. This theorem
    is so
    fundamental because it justifies why a tropical variety (defined
    combinatorially using initial ideals) carries information about
    algebraic varieties: it is the image of an algebraic
    variety over the Puiseux series under the valuation map.
    We want to present the lifting algorithm which allows to
    compute the lift of any given point in the tropical variety of an
    ideal up to prescribed order. The algorithm is implemented using Singular
    and Gfan.

  • Detecting and Handling Degeneracies for Robust Boundar Evaluation
    John Keyser (Texas A & M University)
    Robustness issues pose a problem for many geometric modeling applications. While previous methods have successfully dealt with numerical error issues by using exact computation, problems remain in creating general methods to deal with degeneracies. This poster presents the different parts of our approach for a method to detect and handle degeneracies in boundary evaluation computations. Our implementation takes place in an exact computation framework.

    In order to effectively compute around points that involve degeneracies, we use a system solving approach based on the Rational Univariate Reduction. Our fully exact implementation is based on the toric perturbation approach of Emiris and Canny. With this implementation, we are able to successfully compute surface intersection points. The method enables us to create a thorough test for all major degeneracies arising in boundary evaluation. When degeneracies are detected, we propose the use of a numerical perturbation scheme that eliminates degenerate situations, while minimal algorithmic changes.
  • Static Balancing of Parallel Mechanisms
    Brian Moore (Johann Radon Institute for Computational and Applied Mathematics )
    The design of statically balanced mechanisms consists of deriving a set of
    constraints betweeen kinematic and static parameters such that the center of
    mass remains fixed for any configuration of the mechanism. Such structures
    have several practical applications, including the elimination of vibrations
    which improved both precision and performance.

    Using the four-bar mechanism as an example, we formulate the kinematic
    constraints between the angles and the static balancing constraints as algebraic
    equations over real and complex variables.
    This reduces to the problem of the factorization of Laurent polynomials which
    can be solved using Newton polytopes and Minkowsi sums. Finally, we determine
    necessary and sufficient conditions for statically balanced four-bar mechanisms.

    This is a joint work with Josef Schicho and Clement Gosselin.
  • Real Solving Bivariate Polynomial Systems: Theory and Maple Implementation
    Elias Tsigaridas (Institut National de Recherche en Informatique Automatique (INRIA))
    We present three projection-based algorithms for exact real
    solving of
    well-constrained, bivariate systems of relatively prime
    polynomials.
    Using recent advances in univariate real root isolation and
    extending
    fast algorithms of subsresultant sequences to several variables
    we
    derive a complexity bound of O(N12), where
    N bounds
    the degree
    and the bitsize of the polynomials, improving the previously
    known bound
    by two factors. In the same complexity bound we can also
    compute the
    topology of a real plane algebraic curve.

    We also present a MAPLE implementation of the algorithms, that
    also
    provides univariate real root isolation and basic operations
    with real
    algebraic numbers.