| Institute for Mathematics and its Applications University of Minnesota 400 Lind Hall 207 Church Street SE Minneapolis, MN 55455 |
Web: http://www.ima.umn.edu |
Email: ima-staff@ima.umn.edu |
Telephone: (612) 624-6066 |
Fax: (612) 626-7370
Additional newsletters available at http://www.ima.umn.edu/newsletters
Additional newsletters available at http://www.ima.umn.edu/newsletters
IMA Newsletter #367
May 2007
2006-2007 Program
Applications of Algebraic Geometry
See http://www.ima.umn.edu/2006-2007 for a full description of the 2006-2007 program on Applications of Algebraic Geometry.
News and Notes
As IMA has grown a great deal in the last few years, we have filled out our available space on the fourth floor of Lind Hall. In response to our request for more space, the university of Minnesota has provided us with two suites of offices on the first floor of Lind Hall. The IMA staff have now mostly relocated to these offices. The future visitors of the IMA can check out an access card from the IMA office in 114 Lind Hall to visit the fourth floor as the doors and elevator accessing the fourth floor are kept locked all day.
IMA Events
IMA Annual Program Year Workshop
Non-Linear Computational Geometry
May 29 - June 2, 2007
Organizers: Ioannis Z. Emiris (National University of Athens), Ron Goldman (Rice University), Thorsten Theobald (Johann Wolfgang Goethe-Universität Frankfurt)
Schedule
Tuesday, May 1
| 11:15a-12:15p | IMA postdoc seminar: TBA | Benjamin J. Howard (University of Minnesota Twin Cities) | Lind Hall 215 | PS |
Wednesday, May 2
| 11:15a-12:15p | Algebraic geometry and applications seminar: A homological obstruction to weak order on trees | Patricia Hersh (Indiana University) | Lind Hall 409 | AGS |
Thursday, May 3
| 11:15a-12:15p | Real algebraic geometry tutorial: Some applications of real root counting to mechanics | Richard B. Moeckel (University of Minnesota Twin Cities) | Lind Hall 409 | RAG |
Friday, May 4
| 1:25p-2:25p | IMA/MCIM Industrial problems seminar: Pattern discovery in bioinformatics | Laxmi Parida (IBM Thomas J. Watson Research Center) | Vincent Hall 1 | IPS |
Wednesday, May 9
| 11:15a-12:15p | Alexander Yong, University of Minnesota Algebraic geometry and applications seminar: Schubert combinatorics and geometry | Lind Hall 409 | AGS |
Thursday, May 10
| 11:15a-12:15p | Real algebraic geometry tutorial: Sums of squares of polynomials | Kenneth R. Driessel (Iowa State University) | Lind Hall 409 | RAG |
Tuesday, May 15
| 1:15p-2:15p | Algebraic geometry and applications seminar: Discriminants, dual varieties and toric geometry | Sandra Di Rocco (Royal Institute of Technology (KTH)) | Lind Hall 305 | AGS |
Wednesday, May 16
| 11:15a-12:15p | Algebraic geometry and applications seminar: Average volume, curvatures, and Euler characteristic of random real algebraic varieties | Peter Bürgisser (Universität-GHS Paderborn) | Lind Hall 409 | AGS |
Thursday, May 17
| 11:15a-12:15p | Real algebraic geometry tutorial: Sums of squares of polynomials (continued) | Kenneth R. Driessel (Iowa State University) | Lind Hall 409 | RAG |
Wednesday, May 23
| 11:15a-12:15p | Algebraic geometry and applications seminar: On the Newton polytope of specialized resultants | Ioannis Z. Emiris (National University of Athens) | Lind Hall 409 | AGS |
Thursday, May 24
| 11:15a-12:15p | Real algebraic geometry tutorial: Numerical polynomial algebra | Kenneth R. Driessel (Iowa State University) | Lind Hall 409 | RAG |
Monday, May 28
| All Day | Memorial Day (IMA is closed) |
Tuesday, May 29
| 8:15a-9:00a | Registration and coffee | EE/CS 3-176 | W5.29-6.2.07 | |
| 9:00a-9:15a | Welcome and introduction | Douglas N. Arnold (University of Minnesota Twin Cities) | EE/CS 3-180 | W5.29-6.2.07 |
| 9:15a-10:05a | The bitstream Descartes method | Kurt Mehlhorn (Max-Planck-Institut für Informatik) | EE/CS 3-180 | W5.29-6.2.07 |
| 10:05a-10:40a | Coffee | EE/CS 3-176 | W5.29-6.2.07 | |
| 10:40a-11:30a | Discrete geometry processing with topological guarantees | Dinesh Manocha (University of North Carolina) | EE/CS 3-180 | W5.29-6.2.07 |
| 11:25a-1:30p | Lunch | W5.29-6.2.07 | ||
| 1:30p-2:00p | Resultants of polynomials with two separated variables | Andre Galligo (Université de Nice Sophia Antipolis) | EE/CS 3-180 | W5.29-6.2.07 |
| 2:00p-2:30p | Fast and exact geometric analysis of real algebraic plane curves | Nicola Wolpert (Stuttgart University of Applied Sciences) | EE/CS 3-180 | W5.29-6.2.07 |
| 2:30p-3:10p | Coffee | EE/CS 3-176 | W5.29-6.2.07 | |
| 3:10p-3:40p | The Voronoi diagram of three lines | Sylvain Lazard (Institut National de Recherche en Informatique Automatique (INRIA)-Lorraine) | EE/CS 3-180 | W5.29-6.2.07 |
| 3:50p-4:20p | Second Chances | EE/CS 3-180 | W5.29-6.2.07 | |
| 4:20p-4:30p | Group Photo | EE/CS 3-180 | W5.29-6.2.07 | |
| 4:30p-6:30p | Reception and Poster Session | Lind Hall 400 | W5.29-6.2.07 | |
| Real-time algebraic surface visualization | Tor Dokken (SINTEF) | |||
| The Voronoi circle of smooth closed curves | Ioannis Z. Emiris (National University of Athens) | |||
| Arrangements of real algebraic plane curves | Michael Kerber (Max-Planck-Institut für Informatik) | |||
| Static balancing of parallel mechanisms | Brian Moore (Johann Radon Institute for Computational and Applied Mathematics ) | |||
| Guided surfaces | Jorg Peters (University of Florida) | |||
| Linkage problems and real algebraic geometry | Reinhard Steffens (Johann Wolfgang Goethe-Universität Frankfurt) | |||
| Real solving bivariate polynomial systems: theory and maple implementation | Elias P. Tsigaridas (Institut National de Recherche en Informatique Automatique (INRIA)) |
Wednesday, May 30
| 8:30a-9:00a | Coffee | EE/CS 3-176 | W5.29-6.2.07 | |
| 9:00a-9:50a | New methods for computing the topology of algebraic curves and surfaces | Bernard Mourrain (Institut National de Recherche en Informatique Automatique (INRIA)) | EE/CS 3-180 | W5.29-6.2.07 |
| 9:50a-10:30a | Coffee | EE/CS 3-176 | W5.29-6.2.07 | |
| 10:30a-11:00a | Implicitization of rational surfaces via linear syzygies | Laurent Busé (Institut National de Recherche en Informatique Automatique (INRIA)) | EE/CS 3-180 | W5.29-6.2.07 |
| 11:00a-11:30a | On protocols for the automatic discovery of elementary geometry theorems | Tomas Recio (University of Cantabria) | EE/CS 3-180 | W5.29-6.2.07 |
| 11:30a-1:30p | Lunch | W5.29-6.2.07 | ||
| 1:30p-2:00p | Sextics and spheres | Ciprian S. Borcea (Rider University) | EE/CS 3-180 | W5.29-6.2.07 |
| 2:30p-3:00p | Helly-type theorems for line transversals to disjoint balls | Xavier Goaoc (Institut National de Recherche en Informatique Automatique (INRIA)-Lorraine) | EE/CS 3-180 | W5.29-6.2.07 |
| 3:00p-3:30p | Coffee | EE/CS 3-176 | W5.29-6.2.07 | |
| 3:30p-4:00p | Rational convolution surfaces of quadratic Bezier triangles | Martin Peternell (Technische Universität Wien) | EE/CS 3-180 | W5.29-6.2.07 |
| 4:10p-4:40p | Second Chances | EE/CS 3-180 | W5.29-6.2.07 |
Thursday, May 31
| 8:30a-9:00a | Coffee | EE/CS 3-176 | W5.29-6.2.07 | |
| 9:00a-9:50a | Geometry and computation of mesh surfaces with planar hexagonal faces | Wenping Wang (University of Hong Kong) | EE/CS 3-180 | W5.29-6.2.07 |
| 9:50a-10:30a | Coffee | EE/CS 3-176 | W5.29-6.2.07 | |
| 10:30a-11:20a | Rational surfaces with rational offsets and their applications to blending constructions | Rimvydas Krasauskas (Vilnius State University) | EE/CS 3-180 | W5.29-6.2.07 |
| 11:20a-1:30p | Lunch | W5.29-6.2.07 | ||
| 1:30p-2:00p | Real monoid surfaces | Ragni Piene (University of Oslo) | EE/CS 3-180 | W5.29-6.2.07 |
| 2:00p-2:30p | Approximate implicitization and CAD-type intersection algorithms | Tor Dokken (SINTEF) | EE/CS 3-180 | W5.29-6.2.07 |
| 2:30p-3:10p | Coffee | EE/CS 3-176 | W5.29-6.2.07 | |
| 3:10p-3:40p | Geometric applications of the Bezout matrix in the bivariate tensor-product Lagrange basis | Laureano Gonzalez-Vega (University of Cantabria) | EE/CS 3-180 | W5.29-6.2.07 |
| 3:50p-4:20p | Second Chances | EE/CS 3-180 | W5.29-6.2.07 | |
| 6:30p-8:30a | Group Dinner at Caspian Bistro | Caspian Bistro 2418 University Ave SE Minneapolis, MN 55414 (612) 623-1113 | W5.29-6.2.07 |
Friday, June 1
| 8:30a-9:00a | Coffee | EE/CS 3-176 | W5.29-6.2.07 | |
| 9:00a-9:50a | Application of algebraic geometry to kinematics | Manfred Husty (Leopold-Franzens Universität Innsbruck) | EE/CS 3-180 | W5.29-6.2.07 |
| 9:50a-10:30a | Coffee | EE/CS 3-176 | W5.29-6.2.07 | |
| 10:30a-11:20a | Geometric representation of rigidity-related matroids | Ileana Streinu (Smith College) | EE/CS 3-180 | W5.29-6.2.07 |
| 11:20a-1:30p | Lunch | W5.29-6.2.07 | ||
| 1:30p-2:00p | Geometric and topological inference in the non linear realm: on the importance of singularity theory | Frederic Cazals (Institut National de Recherche en Informatique Automatique (INRIA)) | EE/CS 3-180 | W5.29-6.2.07 |
| 2:00p-2:30p | Bezier subdivision for inverse molecular kinematics | Ming Zhang (University of Texas) | EE/CS 3-180 | W5.29-6.2.07 |
| 2:30p-3:10p | Coffee | EE/CS 3-176 | W5.29-6.2.07 | |
| 3:10p-3:40p | Bezout's theorem and implicitization | Carlos D'Andrea (University of Barcelona) | EE/CS 3-180 | W5.29-6.2.07 |
| 3:50p-4:20p | Second Chances | EE/CS 3-180 | W5.29-6.2.07 |
Saturday, June 2
| 8:30a-9:00a | Coffee | EE/CS 3-176 | W5.29-6.2.07 | |
| 9:00a-9:50a | Algebraic splines for molecular modeling | Chandrajit L. Bajaj (University of Texas) | EE/CS 3-180 | W5.29-6.2.07 |
| 9:50a-10:30a | Coffee | EE/CS 3-176 | W5.29-6.2.07 | |
| 10:30a-11:20a | Topics in curve and surface implicitization | David A. Cox (Amherst College) | EE/CS 3-180 | W5.29-6.2.07 |
| 11:30a-12:00p | Second Chances and closing remarks | EE/CS 3-180 | W5.29-6.2.07 |
Event Legend: |
|
| AGS | Algebraic Geometry and Applications Seminar |
| IPS | Industrial Problems Seminar |
| PS | IMA Postdoc Seminar |
| RAG | Weekly Tutorial: Real Algebraic Geometry |
| W5.29-6.2.07 | Non-Linear Computational Geometry |
Abstracts
| 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 (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. | |
| 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 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. | |
| 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 well-known method of "moving curves" for plane curve implicitization. | |
| Peter Bürgisser (Universität-GHS 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 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. | |
| 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 mu-bases for surface implicitizations, and the resultant of the mu-basis. | |
| 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 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. | |
| 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 co-dimension 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 CAD-type intersection algorithms |
| Abstract: 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. | |
| 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 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. |
|
| Xavier Goaoc (Institut National de Recherche en Informatique Automatique (INRIA)-Lorraine) | Helly-type 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 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. | |
| Laureano Gonzalez-Vega (University of Cantabria) | Geometric applications of the Bezout matrix in the bivariate tensor-product Lagrange basis |
| Abstract: 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 | |
| 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 `Coxeter-like complexes' along the way. | |
| Manfred Husty (Leopold-Franzens 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 (Max-Planck-Institut 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 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) | |
| 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 (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. | |
| 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 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. | |
| Dinesh Manocha (University of North Carolina) | Discrete geometry processing with topological guarantees |
| Abstract: 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. | |
| Kurt Mehlhorn (Max-Planck-Institut für Informatik) | The bitstream Descartes method |
| Abstract: 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(n4 (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 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. | |
| 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 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. | |
| 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 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. | |
| 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 tensor-product patches. This approach yields C2 subdivision surfaces and polynomial C2 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 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. | |
| 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 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. | |
| Reinhard Steffens (Johann Wolfgang Goethe-Universitä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:
|
|
| Ileana Streinu (Smith College) | Geometric representation of rigidity-related matroids |
| Abstract: 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. | |
| Elias P. Tsigaridas (Institut National de Recherche en Informatique Automatique (INRIA)) | Real solving bivariate polynomial systems: theory and maple implementation |
| Abstract: We present three projection-based algorithms for exact real solving of well-constrained, bivariate systems of relatively prime polynomials. Using recent advances in univariate real root isolation and extending fast algorithms of subsresultant sequences to several variables we derive a complexity bound of O(N12), where N bounds the degree and the bitsize of the polynomials, improving the previously known bound by two factors. In the same complexity bound we can also compute the topology of a real plane algebraic curve. We also present a MAPLE implementation of the algorithms, that also provides univariate real root isolation and basic operations with real algebraic numbers. | |
| 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 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. | |
| 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 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. | |
Visitors in Residence
| Pankaj Kumar Agarwal | Duke University | 5/28/2007 - 6/2/2007 |
| Jungha An | University of Minnesota Twin Cities | 9/1/2005 - 8/31/2007 |
| Douglas N. Arnold | University of Minnesota Twin Cities | 7/15/2001 - 8/31/2007 |
| Donald G. Aronson | University of Minnesota Twin Cities | 9/1/2002 - 8/31/2007 |
| Chandrajit L. Bajaj | University of Texas | 5/28/2007 - 6/2/2007 |
| Hélène Barcelo | Arizona State University | 5/7/2007 - 6/1/2007 |
| Saugata Basu | Georgia Institute of Technology | 4/4/2007 - 6/30/2007 |
| Daniel J. Bates | University of Minnesota Twin Cities | 9/1/2006 - 8/31/2007 |
| Arend Bayer | University of Utah | 5/8/2007 - 5/11/2007 |
| Yermal Sujeet Bhat | University of Minnesota Twin Cities | 9/1/2006 - 8/31/2007 |
| Ciprian S. Borcea | Rider University | 5/28/2007 - 6/2/2007 |
| Peter Bürgisser | Universität-GHS Paderborn | 4/11/2007 - 5/18/2007 |
| Laurent Busé | Institut National de Recherche en Informatique Automatique (INRIA) | 5/27/2007 - 6/3/2007 |
| Frederic Cazals | Institut National de Recherche en Informatique Automatique (INRIA) | 5/28/2007 - 6/3/2007 |
| Ionut Ciocan-Fontanine | University of Minnesota Twin Cities | 9/1/2006 - 6/30/2007 |
| David A. Cox | Amherst College | 5/28/2007 - 6/2/2007 |
| Carlos D'Andrea | University of Barcelona | 5/29/2007 - 6/8/2007 |
| Alicia Dickenstein | University of Buenos Aires | 5/23/2007 - 6/2/2007 |
| Jintai Ding | University of Cincinnati | 5/27/2007 - 6/2/2007 |
| Sandra Di Rocco | Royal Institute of Technology (KTH) | 4/4/2007 - 6/4/2007 |
| Tor Dokken | SINTEF | 5/28/2007 - 6/3/2007 |
| Kenneth R. Driessel | Iowa State University | 9/1/2006 - 6/29/2007 |
| Fayssal El Moufatich | Vodafone Group R&D Germany | 5/28/2007 - 6/2/2007 |
| Ioannis Z. Emiris | National University of Athens | 5/2/2007 - 6/2/2007 |
| Makan Fardad | University of Minnesota Twin Cities | 8/26/2006 - 8/13/2007 |
| Michael S. Floater | University of Oslo | 5/28/2007 - 6/2/2007 |
| Andre Galligo | Université de Nice Sophia Antipolis | 5/28/2007 - 6/4/2007 |
| Luis Garcia-Puente | Texas A & M University | 5/29/2007 - 6/3/2007 |
| Xavier Goaoc | Institut National de Recherche en Informatique Automatique (INRIA)-Lorraine | 5/26/2007 - 6/2/2007 |
| Ron Goldman | Rice University | 5/28/2007 - 6/3/2007 |
| Laureano Gonzalez-Vega | University of Cantabria | 5/21/2007 - 6/9/2007 |
| Jason E. Gower | University of Minnesota Twin Cities | 9/1/2006 - 8/31/2007 |
| Milena Hering | University of Minnesota Twin Cities | 9/1/2006 - 8/31/2007 |
| Patricia Hersh | Indiana University | 2/15/2007 - 5/15/2007 |
| Christopher Hillar | Texas A & M University | 5/28/2007 - 6/6/2007 |
| Benjamin J. Howard | University of Minnesota Twin Cities | 9/1/2006 - 8/21/2007 |
| Evelyne Hubert | Institut National de Recherche en Informatique Automatique (INRIA) | 9/1/2006 - 6/30/2007 |
| Manfred Husty | Leopold-Franzens Universität Innsbruck | 5/28/2007 - 6/3/2007 |
| Farhad Jafari | University of Wyoming | 9/1/2006 - 6/30/2007 |
| Ravi Janardan | University of Minnesota Twin Cities | 5/29/2007 - 6/2/2007 |
| Itnuit Janovitz-Freireich | North Carolina State University | 5/29/2007 - 6/2/2007 |
| Anders Nedergaard Jensen | Aarhus University | 9/6/2006 - 6/30/2007 |
| Gabriela Jeronimo | University of Buenos Aires | 4/15/2007 - 6/9/2007 |
| Steve Kaliszewski | Arizona State University | 1/7/2007 - 6/30/2007 |
| Mordechai Katzman | University of Sheffield | 1/10/2007 - 5/15/2007 |
| Michael Kerber | Universität Kaiserslautern | 2/19/2007 - 5/11/2007 |
| Michael Kerber | Max-Planck-Institut für Informatik | 5/27/2007 - 6/3/2007 |
| Michael Kettner | Georgia Institute of Technology | 5/28/2007 - 6/6/2007 |
| John Keyser | Texas A & M University | 5/28/2007 - 6/2/2007 |
| Rimvydas Krasauskas | Vilnius State University | 5/20/2007 - 6/20/2007 |
| Song-Hwa Kwon | University of Minnesota Twin Cities | 8/30/2005 - 8/31/2007 |
| Oliver Labs | Universität des Saarlandes | 5/28/2007 - 6/3/2007 |
| Niels Lauritzen | Aarhus University | 8/28/2006 - 7/10/2007 |
| Sylvain Lazard | Institut National de Recherche en Informatique Automatique (INRIA)-Lorraine | 5/28/2007 - 6/3/2007 |
| Anton Leykin | University of Minnesota Twin Cities | 8/16/2006 - 8/15/2007 |
| Hstau Y Liao | University of Minnesota Twin Cities | 9/2/2005 - 8/31/2007 |
| Laura Lurati | University of Minnesota Twin Cities | 9/1/2006 - 8/31/2007 |
| Gennady Lyubeznik | University of Minnesota Twin Cities | 9/1/2006 - 6/30/2007 |
| Dinesh Manocha | University of North Carolina | 5/28/2007 - 5/29/2007 |
| Hannah Markwig | University of Minnesota Twin Cities | 9/1/2006 - 8/31/2007 |
| Thomas Markwig | Universität Kaiserslautern | 9/1/2006 - 6/30/2007 |
| Kurt Mehlhorn | Max-Planck-Institut für Informatik | 5/28/2007 - 6/1/2007 |
| Richard B. Moeckel | University of Minnesota Twin Cities | 9/1/2006 - 6/30/2007 |
| Brian Moore | Johann Radon Institute for Computational and Applied Mathematics | 5/28/2007 - 6/2/2007 |
| Bernard Mourrain | Institut National de Recherche en Informatique Automatique (INRIA) | 5/27/2007 - 6/3/2007 |
| Uwe Nagel | University of Kentucky | 9/1/2006 - 6/1/2007 |
| Jiawang Nie | University of Minnesota Twin Cities | 9/1/2006 - 8/31/2007 |
| Michael E. O'Sullivan | San Diego State University | 4/12/2007 - 5/11/2007 |
| Laxmi Parida | IBM Thomas J. Watson Research Center | 5/3/2007 - 5/6/2007 |
| Dmitrii Pasechnik | Nanyang Technological University | 5/14/2007 - 6/14/2007 |
| Martin Peternell | Technische Universität Wien | 5/28/2007 - 6/3/2007 |
| Jorg Peters | University of Florida | 5/28/2007 - 6/2/2007 |
| Ragni Piene | University of Oslo | 5/28/2007 - 6/2/2007 |
| Bharath Rangarajan | University of Minnesota Twin Cities | 5/29/2007 - 6/2/2007 |
| Tomas Recio | University of Cantabria | 5/28/2007 - 6/3/2007 |
| Victor Reiner | University of Minnesota Twin Cities | 9/1/2006 - 6/30/2007 |
| Joel Roberts | University of Minnesota Twin Cities | 9/1/2006 - 6/30/2007 |
| Marie Rognes | University of Oslo | 1/10/2007 - 6/30/2007 |
| J. Maurice Rojas | Texas A & M University | 4/11/2007 - 6/3/2007 |
| Bjarke Hammersholt Roune | Aarhus University | 9/12/2006 - 6/30/2007 |
| David Rusin | Northern Illinois University | 5/27/2007 - 6/2/2007 |
| Arnd Scheel | University of Minnesota Twin Cities | 7/15/2004 - 8/31/2007 |
| Chehrzad Shakiban | University of Minnesota Twin Cities | 9/1/2006 - 8/31/2007 |
| Milind Sohoni | Indian Institute of Technology | 4/13/2007 - 5/18/2007 |
| Frank Sottile | Texas A & M University | 2/26/2007 - 6/30/2007 |
| Steven Sperber | University of Minnesota Twin Cities | 9/1/2006 - 6/30/2007 |
| Reinhard Steffens | Johann Wolfgang Goethe-Universität Frankfurt | 5/28/2007 - 6/3/2007 |
| Ileana Streinu | Smith College | 5/28/2007 - 6/2/2007 |
| Rebecca Swanson | Indiana University | 5/3/2007 - 5/16/2007 |
| Agnes Szanto | North Carolina State University | 5/28/2007 - 6/1/2007 |
| Thorsten Theobald | Johann Wolfgang Goethe-Universität Frankfurt | 5/28/2007 - 6/2/2007 |
| Louis Theran | University of Massachusetts | 5/28/2007 - 6/2/2007 |
| Carl Toews | University of Minnesota Twin Cities | 9/1/2005 - 8/31/2007 |
| Elias P. Tsigaridas | Institut National de Recherche en Informatique Automatique (INRIA) | 5/26/2007 - 6/3/2007 |
| John Voight | University of Minnesota Twin Cities | 8/15/2006 - 8/31/2007 |
| Wenping Wang | University of Hong Kong | 5/28/2007 - 6/2/2007 |
| Nicola Wolpert | Stuttgart University of Applied Sciences | 5/27/2007 - 6/3/2007 |
| William Wood | Corning | 5/28/2007 - 6/3/2007 |
| Fei Yang | University of Minnesota Twin Cities | 5/29/2007 - 6/2/2007 |
| Josephine Yu | University of California | 1/9/2007 - 6/30/2007 |
| Hongchao Zhang | University of Minnesota Twin Cities | 9/1/2006 - 8/31/2007 |
| Ming Zhang | University of Texas | 5/31/2007 - 6/3/2007 |
| Severinas Zube | Vilnius State University | 5/28/2007 - 6/3/2007 |
Legend:
Postdoc or Industrial Postdoc
Long-term Visitor
IMA Affiliates:
3M, Boeing, Carnegie-Mellon University, Corning, ExxonMobil, Ford, General Electric, General Motors, Georgia Institute of Technology, Honeywell, IBM, Indiana University, Iowa State University, Johnson & Johnson, Kent State University, Lawrence Livermore National Laboratory, Lockheed Martin, Los Alamos National Laboratory, Medtronic, Michigan State University, Michigan Technological University, Mississippi State University, Motorola, Northern Illinois University, Ohio State University, Pennsylvania State University, Purdue University, Rice University, Rutgers University, Sandia National Laboratories, Schlumberger-Doll, Schlumberger-Doll Research, Seoul National University, Siemens, Telcordia, Texas A & M University, University of Chicago, University of Cincinnati, University of Delaware, University of Houston, University of Illinois at Urbana-Champaign, University of Iowa, University of Kentucky, University of Maryland, University of Michigan, University of Minnesota, University of Notre Dame, University of Pittsburgh, University of Texas, University of Wisconsin, University of Wyoming, US Air Force Research Laboratory, Wayne State University, Worcester Polytechnic Institute