May 29 - June 2, 2007
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^{4} (log(1/ρ) + τ)^{2}) 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^{2} subdivision surfaces and
polynomial C^{2} 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))^{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
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.
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^{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.
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.