This talk shall describe a survey of algebraic spline (A-spline and A-patch) 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.

A generic configuration of three spheres determines several sextic curves, all related to the curve of common tangents. First among them, the direction-sextic, 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.

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 well-known method of "moving curves" for plane curve implicitization.

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 so-called ridges), and the calculation of the Morse-Smale complex of the distance function to points in 3D space (the so-called flow complex). We shall conclude with perspectives arising in trying to generalize such approaches in higher dimension.

This lecture will discuss several topics related to curve and surface implicitization, including the structure of the moving curve ideal, the construction of mu-bases for surface implicitizations, and the resultant of the mu-basis.

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 non-trivial 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.

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.

When developing CAD-type intersection algorithms for NonUniform Rational B-splines 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 CAD-type intersection algorithms addressing self-intersecting CAD-surfaces, and singular and near singular intersection of NURBS surfaces.

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.

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 bi-variate 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.

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.

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 k-planes (also called k-flats) that intersect all elements of a given family of subsets (or objects) in Rd. These are the k-transversals of the given family and they define a certain subspace of the corresponding Grassmannian.

I will present recent results on Helly-type theorems for the existence of line transversals to disjoint balls obtained in collaboration with Ciprian Borcea, Otfried Cheong, Andreas Holmsen and Sylvain Petitjean.

Using a new formulation of the Bezout matrix, we construct bivariate matrix polynomials expressed in a tensor-product Lagrange basis. We use these matrix polynomials to solve common tasks in computer-aided 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

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.

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.

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)

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.

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 (PN-surfaces) 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 PN-surfaces are used, and what is their lowest parametrization degree. We follow Laguerre geometric approach to the theory of PN-surfaces and use a universal rational parametrization of the Blaschke cylinder. This allows us to generate new low degree analytic solutions for PN-surface 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.

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.

We give a complete description of the Voronoi diagram of three lines in three-dimensional 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 non-singular 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 semi-algebraic tests for separating the two connected components of each two-dimensional 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 semi-algebraic tests.

Our goal is to compute reliable solutions for many non-linear 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 two-sided 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 collision-free paths.

The Descartes method is an algorithm for isolating the real roots of square-free polynomials with real coefficients. We assume that coefficients are given as (potentially infinite) bit-streams. 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 bit-stream coefficients. To isolate the real roots of a square-free 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⁴ (log(1/ρ) + τ)²) bit operations. We also report on computational experience with the algorithm.

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.

Computing the topology of a geometric object defined implicitly appears in many geometric modeling problems, such as surface-surface intersection, self-intersection, 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 algebraic-geometric modeler AXEL will shortly demonstrated.

In the present talk it will be shown that polynomial quadratic triangular Bezier surfaces are LN-surfaces 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.

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² subdivision surfaces and polynomial C² surfaces, typically with good curvature distribution.

A monoid surface is a surface of degree d which has a singular point of multiplicity d-1. 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.

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 Recio-Velez, 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 non-degeneracy 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.

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))ⁿ⁺¹ 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), assuming k

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.

Sparsity matroids generalize the combinatorics behind several types of rigidity (2D bar-and-joint, arbitrary dimension body-and-bar, 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.

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 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.

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.

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 x-coordinate a are found with adaptive-precision 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 Gonzalez-Vega and Necula (2002), and with cad2d by Brown demonstrate its efficiency.

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 ligand-receptor docking, ab initio prediction of protein structure, and protein folding. In this talk, we focus on a specific geometry-constrained conformational searching problem, where some feature atoms have pre-specified 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.

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.