# <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:- Given a rigid graph with prescribed edge lengths, how

many

embeddings are there? - 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.- Given a rigid graph with prescribed edge lengths, how
**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 C^{2}subdivision surfaces and

polynomial C^{2}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(n^{1}1),

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(N*), where^{12}*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.