
Alexander Yong, University of Minnesota
Algebraic geometry and applications seminar: Schubert combinatorics and geometry 
Abstract: The topic of Schubert varieties of homogeneous spaces G/P
is at the interface between algebraic geometry and combinatorics.
I'll describe work on two themes.
The first is Schubert calculus: counting points in intersections
of Schubert varieties. A goal has been combinatorial rules for these
computations. I'll explain the carton rule which manifests basic
symmetries
of the numbers for the Grassmannian case; this version also has the
advantage
of generalizing to (co)minuscule G/P.
The second concerns singularities of Schubert varieties. I'll give a
combinatorial framework for understanding invariant of singularities via a
notion we call interval pattern avoidance.
The first half of this talk is joint work with Hugh Thomas (U. New
Brunswick)
while the second half is joint work with Alexander Woo (UC Davis).

Chandrajit L. Bajaj (University of Texas) 
Algebraic splines for molecular modeling 
Abstract: This talk shall describe a survey of algebraic spline
(Aspline and Apatch)
construction techniques for capturing molecular surfaces and implicit solvation
shells (models for molecules in their watery environment). These molecular
surfaces are obtained from either atomic 3D coordinates (scattered data) of the
molecule, or segmented 3D electron microscopy maps (dense data). For 3D maps at
5 20 Angstrom resolution, I shall also present algebraic spline algorithms to
detect and represent secondary (helices, sheets) and/or tertiary (sandwiches,
barrels, etc.) structural molecular models. For these latter algorithms, we
employ techniques from computational algebraic geometry and differential
topology, especially the computation of stable/unstable manifolds of certain
critical points of distance functions of molecular surface boundaries.

Ciprian S. Borcea (Rider University) 
Sextics and spheres 
Abstract: A generic configuration of three spheres determines several sextic
curves, all related to the curve of common tangents. First among them,
the directionsextic, which records only the direction of these
tangents, retains in fact, as a planar projective complex curve,
enough information for reconstructing the sphere configuration, up to
similarity.
I shall discuss properties of this family of sextics and the resulting
criterion for classifying configurations. 
Laurent Busé (Institut National de Recherche en Informatique Automatique (INRIA)) 
Implicitization of rational surfaces via linear syzygies 
Abstract: Surface implicitization, i.e. finding the implicit equation of an algebraic surface defined parametrically, is a classical problem and there are numerous approaches to its solution. In this talk, we will show that the linear syzygies of the parametrization of a rational surface can be used to represent and to compute its implicit equation under suitable conditions. This is, in some sense, a natural generalization of the wellknown method of "moving curves" for plane curve implicitization. 
Peter Bürgisser (UniversitätGHS Paderborn) 
Algebraic geometry and applications seminar: Average volume, curvatures, and Euler characteristic of random real algebraic varieties 
Abstract: We determine the expected curvature polynomial of random real projective
varieties given as the zero set of independent random polynomials with
Gaussian distribution, whose distribution is invariant under the action
of the orthogonal group. In particular, the expected Euler
characteristic of such random real projective varieties is found. This
considerably extends previously known results on the number of roots,
the volume, and the Euler characteristic of the solution set of random
polynomial equations. 
Frederic Cazals (Institut National de Recherche en Informatique Automatique (INRIA)) 
Geometric and topological inference in the non linear realm: on the
importance of singularity theory 
Abstract: In the non linear realm, a powerful way to describe complex shapes is
in terms of stratifications, that is topological disks together with
the proper incidences, so as to define some kind of complex (cell, CW,
etc). In particular, singularity theory provides a convenient way to
specify such incidences through local normal forms, the parametric
form of the topological disks depending on the particular problem
investigated. We shall review two examples illustrating this
framework in 3D : the detection of loci of extremal curvature of
smooth surfaces (the socalled ridges), and the calculation of the
MorseSmale complex of the distance function to points in 3D space
(the socalled flow complex). We shall conclude with perspectives
arising in trying to generalize such approaches in higher dimension. 
David A. Cox (Amherst College) 
Topics in curve and surface implicitization 
Abstract: This lecture will discuss several topics related to curve and surface implicitization, including the structure of the moving curve ideal, the construction of mubases for surface implicitizations, and the resultant of the mubasis. 
Carlos D'Andrea (University of Barcelona) 
Bezout's theorem and implicitization 
Abstract: This is a joint work with Martin Sombra.
The computation of the implicit equations of polynomial and rational parametrizations is always a hot topic in Computational Algebraic Geometry and CAGD. Recently, a lot of attention has been given to the computation of the Newton Polytope of the implicit equation, given the supports of the parametrization (sparse philosophy).
In this talk, we will show how the use of classical intersection theory in the torus can give us nontrivial information about this Newton Polytope. As an application of these results, we can give a complete description of the Newton Polytope of the implicit equation of a generic plane rational curve. 
Sandra Di Rocco (Royal Institute of Technology (KTH)) 
Algebraic geometry and applications seminar: Discriminants, dual varieties and toric geometry 
Abstract: Given an algebraic variety, embedded in projective space, the closure of all
hyperplanes
tangent at some non singular point is called the dual variety. A general
embedding has
dual variety of codimension one (in the dual projective space) and hence
defined by
an irreducible homogeneous polynomial, called the discriminant.
The study of the exceptional embeddings, i.e. the ones having dual variety
of lower dimension,
is a very classical problem in algebraic geometry, still open for many
classes of varieties.
I will explain the problem and give the solution for the class of non
singular toric varieties. 
Tor Dokken (SINTEF) 
Approximate implicitization and CADtype intersection
algorithms 
Abstract: When developing CADtype intersection algorithms for
NonUniform Rational Bsplines surfaces (NURBS) is important
to ensure that the algorithm identifies all intersection
branches. For transversal intersections this is fairly
straight forward. For singular or near singular intersection,
when the surfaces are close and near parallel, the
traditional approach of recursive subdivision does not
suffice on its own. The use of algebraic surfaces to separate
near parallel not intersecting surfaces reduces the depth of
recursion. Approximate implicitization denotes methods that
approximate piecewise parametric manifolds p(s) with an
algebraic hypersurface q(x)=0. The talk will address the
approach to approximate implicitization already published by
the author and further report on how approximate
implicitization has helped the development of a CADtype
intersection algorithms addressing selfintersecting
CADsurfaces, and singular and near singular intersection of
NURBS surfaces. 
Kenneth R. Driessel (Iowa State University) 
Real algebraic geometry tutorial: Numerical polynomial algebra 
Abstract: See the book "Numerical Polynomial Algebra" by
H. J. Stetter, SIAM, 2004. 
Ioannis Z. Emiris (National University of Athens) 
The Voronoi circle of smooth closed curves 
Abstract: 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. 
Andre Galligo (Université de Nice Sophia Antipolis) 
Resultants of polynomials with two separated variables 
Abstract: The intersection curve C of two surfaces parameterized by
polynomials
is defined by 3 equations:
F(s,t) = G(u,v)
and its geometry can be studied via its projection E on the
(s,u)space.
The equation of E is obtained by elimination of the two
separated variables
t and v. This is done by the computation of a special
bivariate resultant.
I will present this new resultant which was introduced in a
joint paper with
L. Buse and M. Elkadi and further studied in a joint work with
M. Elkadi. 
Xavier Goaoc (Institut National de Recherche en Informatique Automatique (INRIA)Lorraine) 
Hellytype theorems for line transversals to disjoint balls 
Abstract: Helly's theorem of 1923 opened a large field of inquiry now
designated
as geometric transversal theory. A typical concern is the
study of all
kplanes (also called kflats) that intersect all elements of
a given
family of subsets (or objects) in Rd. These are the
ktransversals of
the given family and they define a certain subspace of the
corresponding Grassmannian.
I will present recent results on Hellytype theorems for the
existence
of line transversals to disjoint balls obtained in
collaboration with
Ciprian Borcea, Otfried Cheong, Andreas Holmsen and Sylvain
Petitjean. 
Laureano GonzalezVega (University of Cantabria) 
Geometric applications of the Bezout matrix in the bivariate
tensorproduct Lagrange basis 
Abstract: Using a new formulation of the Bezout matrix, we construct bivariate
matrix polynomials expressed in a tensorproduct Lagrange basis. We
use these matrix polynomials to solve common tasks in computeraided
geometric design:
for example, we show that these bivariate polynomials can serve as
stable and efficient implicit epresentations of plane
curves for a variety of curve intersection problems including offset
manipulation.
This is a joint work with D. Aruliah, R. Corless and A. Shakoori

Patricia Hersh (Indiana University) 
Algebraic geometry and applications seminar: A homological obstruction to weak order on trees 
Abstract: When sorting data on a network of computers, it is natural to ask which
data swaps between neighbors constitute progress. In a linear array,
the answer is simple, by virtue of the fact that permutations admit
pleasant notions of inversions and weak order. I will discuss how the
topology of chessboard complexes constrains the extent to which these
ideas may carry over to other trees; it turns out that there are
homological obstructions telling us that a tree does not admit an
inversion function unless each node has at least as much capacity as
its degree minus one. On the other hand, we construct an inversion
function and weak order for all trees that do meet this capacity
requirement, and we prove a connectivity bound conjectured by Babson
and Reiner for `Coxeterlike complexes' along the way. 
Manfred Husty (LeopoldFranzens Universität Innsbruck) 
Application of algebraic geometry to kinematics 
Abstract: Algebraic methods in connection with classical multidimensional geometry have
proven to be very efficient in the computation of direct and inverse kinematics
of mechanisms as well as the explanation of strange, pathological behaviour of
mechanical systems. Generally one can say that every planar, spherical or
spatial mechanism having revolute or prismatic joints can be described by
systems of algebraic equations. In this talk we give an overview of the results
achieved within the last years using algebraic geometric methods, geometric
preprocessing and numerical analysis. We provide the mathematical and
geometrical background, like Study's parametrization of the Euclidean motion
group, the ideals belonging to mechanism constraints The methods are explained
with different examples from mechanism analysis and synthesis. 
Michael Kerber (MaxPlanckInstitut für Informatik) 
Arrangements of real algebraic plane curves 
Abstract: We present a complete and exact algorithm for computing the arrangement of algebraic curve segments, based on the generic sweepline 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 sweepline 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 SturmHabicht sequences; numerical methods both speedup the analysis of curves and curve pairs in generic cases, and also find nongeneric cases during the analysis. Nongeneric positions are transformed to generic ones by a change of coordinates, but a subsequent backtransformation provides the results in the original coordinate system.
A preliminary version of the algorithm has been implemented in the EXACUSlibrary AlciX.
(joint work with Arno Eigenwillig) 
Rimvydas Krasauskas (Vilnius State University) 
Rational surfaces with rational offsets and their applications to
blending constructions 
Abstract: A surface offsetting operation in CAGD (Computer Aided Geometric Design)
involves sophisticated approximation techniques, since an offset of a general
rational surface is not rational. On the other hand, a class of rational
surfaces with rational offsets (PNsurfaces) includes main primitive surfaces
in CAGD: i.e. natural quadrics (sphere, circular cylinders and cones), torus,
and also their generalizations: Dupin cyclides and rational canal surfaces.
Therefore, it is important to understand what geometric modeling constructions
are possible if only PNsurfaces are used, and what is their lowest
parametrization degree. We follow Laguerre geometric approach to the theory of
PNsurfaces and use a universal rational parametrization of the Blaschke
cylinder. This allows us to generate new low degree analytic solutions for
PNsurface blendings between the following pairs: plane/natural quadric, two
natural quadrics and natural quadric/Dupin cyclide. Applications will be
illustrated by recent implementations in a commercial CAD software package. 
Sylvain Lazard (Institut National de Recherche en Informatique Automatique (INRIA)Lorraine) 
The Voronoi diagram of three lines 
Abstract: We give a complete description of the Voronoi diagram of three lines in
threedimensional real space. In particular, we show that the topology of the Voronoi diagram is
invariant for three lines in general position, that is, that are pairwise skew
and not all parallel to a common plane. The trisector consists of four
unbounded branches of either a nonsingular quartic or of a cubic and line
that do not intersect in real space. Each cell of dimension two consists of
two connected components on a hyperbolic paraboloid that are bounded,
respectively, by three and one of the branches of the trisector. The proof
technique, which relies heavily upon modern tools of computer algebra, is of
interest in its own right.
This characterization yields some fundamental properties of the Voronoi
diagram of three lines. In particular, we present linear semialgebraic tests
for separating the two connected components of each twodimensional Voronoi
cell and for separating the four connected components of the trisector. This
enables us to answer queries of the form, given a point, determine in which
connected component of which cell it lies. We also show that the arcs of the
trisector are monotonic in some direction. These properties imply that points
on the trisector of three lines can be sorted along each branch using only
linear semialgebraic tests. 
Dinesh Manocha (University of North Carolina) 
Discrete geometry processing with topological guarantees 
Abstract: Our goal is to compute reliable solutions for many nonlinear
geometric problems that arise in geometric modeling, computer
graphics and robotics. Prior methods for solving these problems can be
classified into exact and approximate approaches. The exact algorithms are
able to guarantee correct output, but are
usually difficult to implement reliably and efficiently. On the
other
hand, current approximate techniques may not provide any
topological
guarantees on the solution. We bridge the gap between these two
approaches, by developing a unified sampling based approach to
solve these problems with topological guarantees. Specifcally, we
present results for surface extraction and motion planning problems.
Surface extraction problems include Boolean operations,
implicit
surface polygonization and Minkowski sum evaluation.
We compute an approximate boundary of the final solid defined
by
these operations. Our algorithm computes an approximation
that is guaranteed to be topologically equivalent to the exact
surface and bounds the approximation error using twosided
Hausdorff error.
We demonstrate the performance of our approach for the
following
applications: Boolean operations on complex polyhedral models
and
low degree algebraic primitives, model simplification and
remeshing
of polygonal models, and Minkowski sums and offsets of
complex polyhedral models.
The second class of problems is motion planning of rigid or
articulated robots translating or rotating among stationary
obstacles. We present an
algorithm for complete motion planning, i.e., find a path if
one
exists and report a failure otherwise. Our algorithm performs
deterministic sampling to compute a roadmap that captures the
connectivity of the free space and combines with randomized
sampling and cell decomposition to further improve the performance. We
demonstrate the performance of our algorithm on a number of
challenging environments with narrow passages and no collisionfree paths. 
Kurt Mehlhorn (MaxPlanckInstitut für Informatik) 
The bitstream Descartes method 
Abstract: The Descartes method is an algorithm for isolating the real
roots of squarefree polynomials
with real coefficients. We assume
that coefficients are given as (potentially infinite)
bitstreams. In other
words, coefficients can be approximated to any desired
accuracy, but are not
known exactly. We show that
a variant of the Descartes algorithm can cope with bitstream
coefficients. To isolate the real roots of a
squarefree real polynomial q(x) of degree n, root separation
ρ, coefficients bounded by
2 to the τ, and leading coefficient at least one, the
algorithm needs coefficient approximations
with O(n(log(1/ρ) + τ)) bits after the binary point and has
an expected cost of
O(n^{4} (log(1/ρ) + τ)^{2}) bit operations. We also report on
computational experience with
the algorithm.

Richard B. Moeckel (University of Minnesota Twin Cities) 
Real algebraic geometry tutorial: Some applications of real root counting to mechanics 
Abstract: This talk is intended to illustrate some of the methods covered last semester in the real algebraic geometry tutorial. I will describe some problems from celestial mechanics which can be reduced to counting real roots of systems of polynomial equations. I will show how to solve some of the simplest ones by using Sturm's algorithm and Hermite root counting and will mention several open problems. 
Brian Moore (Johann Radon Institute for Computational and Applied Mathematics ) 
Static balancing of parallel mechanisms 
Abstract: 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 fourbar 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 fourbar mechanisms.
This is a joint work with Josef Schicho and Clement Gosselin. 
Bernard Mourrain (Institut National de Recherche en Informatique Automatique (INRIA)) 
New methods for computing the topology of algebraic curves and surfaces 
Abstract: Computing the topology of a geometric object defined implicitly appears in
many geometric modeling problems, such as surfacesurface intersection,
selfintersection, arrangement computation problems ...
It is a critical step in the analysis and approximation of (semi)algebraic
curves or surfaces, encountered in these geometric operations.
Its difficulties are mainly due to the presence of singularities on these
algebraic objects and to the analysis of the geometry near these singular
points.
The classical approach which has been developed for algebraic curves
in the plane projects the problem onto a line, detects the value which are
critical for this projection and lift points back on the curve at these
critical values and in between. Information on the number of branches at
these critical values or genericity condition tests on the number of critical
points above a value of the projection have to be computed, in order to be
able to perform correctly the combinatorial connection step of these
algorithms. This approach has also been extended to curves and surfaces in
3D.
In the talk, we will consider methods which requires information on the
boundary of regions instead of information at critical points. We will
describe a new method for computing the topology of planar implicit curves,
which proceed by subdivision and which only requires the isolation of
extremal points. Extension of this approach to curves and surfaces in 3D will
be described. Experimentation of these algorithms based on the subdivision
solvers of the library SYNAPS and the algebraicgeometric modeler AXEL will
shortly demonstrated. 
Laxmi Parida (IBM Thomas J. Watson Research Center) 
IMA/MCIM Industrial problems seminar: Pattern discovery in bioinformatics 
Abstract: In this talk we look at the combinatorics and statistics of patterns that computational biologists discover at different levels in biological data be it nucleic acid sequence, microarray data or other formal structures. Is there a commonality that runs across these various domains? Can we apply the lessons learned in one domain in another? In this talk we focus on an interesting class of patterns called permutation patterns. We apply these mathematical structures to some problems arising naturally in the area of computational biology such as the problem of common gene clusters across species, phylogeny within populations, and the task of modeling complex control of transcriptions via motifs. In each of these cases we identify the underlying mathematical problems and show some promising results of applying the proposed solutions to biological data. We also discuss the problem of formulating and computing the statistical significance of the permutations motifs in the different domains.

Martin Peternell (Technische Universität Wien) 
Rational convolution surfaces of quadratic Bezier triangles 
Abstract: In the present talk it will be shown that polynomial quadratic triangular
Bezier surfaces are LNsurfaces which means that their normal vector field
n(u,v) can be parametrized by linear coordinate functions.
The close relation to quadratic Cremona transformations in the parameter
domain is elucidated. These reparameterizations
can be used for the computation of convolution surfaces. 
Jorg Peters (University of Florida) 
Guided surfaces 
Abstract: 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 tensorproduct
patches.
This approach yields C^{2} subdivision surfaces and
polynomial C^{2} surfaces, typically with good curvature
distribution.

Ragni Piene (University of Oslo) 
Real monoid surfaces 
Abstract: A monoid surface is a surface of degree d which has a singular point of
multiplicity d1. Any monoid surface admits a rational parameterization,
hence is of potential interest in computer aided geometric design. The
possible real forms of the singularities on a monoid surface are
determined. These results are applied to the classification of quartic
monoid surfaces and a study of a stratification of the parameter space of
these surfaces. A part of this work is joint with M. Løberg and P.H.
Johansen, the other part is due to P.H. Johansen. 
Tomas Recio (University of Cantabria) 
On protocols for the automatic discovery of elementary geometry theorems 
Abstract: Joint work with work with G. Dalzotto and A. Montes.
In the talk we will deal with automatic discovery of elementary geometry theorems, through the algebraic geometry framework that has already shown its success for automatic theorem proving. Automatic discovery of theorems addresses the case of statements that are false in most relevant cases. It aims to produce, automatically, complementary hypotheses for the given statement to become correct. For example, we can draw a triangle and, then, the feet of the corresponding altitudes. These feet are the vertices of a new triangle, the so called "orthic" triangle for the given triangle. We want this orthic triangle to be equilateral, but it is not so, in general. Thus we impose as a thesis that the orthic triangle is equilateral and we expect our method to find the more general situations in which this is going to happen.
In the talk we do not start providing a method, but stating a general framework for discovery, a kind of general protocol. Namely, we begin collecting the conditions that a couple of ideals, each one
belonging to different set of variables–ideally related to the degrees of freedom of the geometric situation–, should verify in order to express necessary and sufficient conditions for the given thesis to hold. Such couple of ideals (named here as a FSDIC) will contribute for some extra hypothesis of equality (respectively, of inequality) type that are required for the theorem to hold.
It will be shown, through examples, that such couple does not always exist (and it is, in general, not unique). But, if it exists, then we can identify and construct a particular FSDIC, that turns out to be very close to the output of the method presented in RecioVelez, Journal of Automated Reasoning, 23, (1999). A test for the existence of a FSDIC will be then stated. Next we will explore the meaning of FSDIC for wise choices of variables (ie. when we deal with "interesting" variables), but we will also remark its limitations in other contexts.
We will show how the inclusion "a priori", as part of the hypotheses, of some nondegeneracy conditions, could help computing through the discovery protocol we are considering. And, then, we will observe how this inclusion can be done through two (apparently similar) methods, but that the choice of one or the other has, sometimes, different consequences and requires human decision.
Finally we will exhibit a collection of examples achieved via different methods, including, in particular, the use of Montes' MCCGS (minimal canonical comprehensive Groebner basis), that yields some results surprisingly close to our geometric intuition.

Reinhard Steffens (Johann Wolfgang GoetheUniversität Frankfurt) 
Linkage problems and real algebraic geometry 
Abstract: 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 1degreeoffreedom linkage, how can one
characterize
and compute the trajectory of the vertices?
From the real algebraic point of view, these questions are
questions
of speciallystructured 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 Hennebergtype graphs) naturally arise from
mixed volumes and Bernstein's theorem.

Ileana Streinu (Smith College) 
Geometric representation of rigidityrelated matroids 
Abstract: Sparsity matroids generalize the combinatorics behind several types of rigidity (2D barandjoint, arbitrary dimension bodyandbar, etc.). A conspicuous open problem is to find geometric representations for ALL of them. We present some partial answers. This is joint work with Louis Theran from UMass Amherst. 
Elias P. Tsigaridas (Institut National de Recherche en Informatique Automatique (INRIA)) 
Real solving bivariate polynomial systems: theory and maple implementation 
Abstract: We present three projectionbased algorithms for exact real
solving of
wellconstrained, 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^{12}), 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. 
Wenping Wang (University of Hong Kong) 
Geometry and computation of mesh surfaces with planar hexagonal faces 
Abstract: Joint work with Yang Liu.
Motivated by applications in modeling glass structures in
architecture, we consider the geometry and computation of mesh
surfaces with planar hexagonal faces from the point of view
of discrete differential geometry. It is shown that the
mesh structure is naturally related to conjugate curve networks on
its underlying smooth surface; furthermore, the shape of each
hexagonal face is in the limit related to the Dupin indicatrix.
These results are used in combination with an optimization method
to compute a mesh surface with planar hexagonal faces to approximate
a given smooth surface.

Nicola Wolpert (Stuttgart University of Applied Sciences) 
Fast and exact geometric analysis of real algebraic plane
curves 
Abstract: An algorithm is presented for the geometric analysis of an algebraic curve
f (x,y) = 0 in the real affine plane. It computes a cylindrical algebraic decomposition
(CAD) of the plane, augmented with adjacency information.
The adjacency information describes the curve’s topology by a topologically
equivalent planar graph. The numerical data in the CAD gives an embedding
of the graph.
The algorithm is designed to provide the exact result for all inputs but to
perform only few symbolic operations for the sake of efficiency. In particular,
the roots of f (a,y) at a critical xcoordinate a are found with adaptiveprecision arithmetic in all cases,
using a variant of the Bitstream Descartes method (Eigenwillig et al., 2005). The algorithm may
choose a generic coordinate system for parts of the analysis but provides its result in the original system.
The algorithm has been implemented as C++ library AlciX in the EXACUS
project. Running time comparisons with top by GonzalezVega and
Necula (2002), and with cad2d by Brown demonstrate its efficiency. 
Ming Zhang (University of Texas) 
Bezier subdivision for inverse molecular kinematics 
Abstract: Conformational searching is a core task in inverse molecular
kinematics. Algorithmic improvements affecting either the speed or
quality of conformational searching will have a profound impact on
applications including ligandreceptor docking, ab initio prediction
of protein structure, and protein folding. In this talk, we focus on a
specific geometryconstrained conformational searching problem, where
some feature atoms have prespecified target positions. Using Bezier
subdivision, we present a method to locate and approximate the
solutions of the equations derived from constraints on the feature
atoms. The conformations corresponding to these solutions are all the
conformations satisfying the target constraints. Three implementations
of the subdivision method taking advantage of the sparsity of the
coefficients of the polynomial equations are presented and the results
are compared. 