# Schedule for: 16w5115 - Computational Algebra and Geometric Modeling

Beginning on Sunday, August 7 and ending Friday August 12, 2016

All times in Oaxaca, Mexico time, CDT (UTC-5).

Sunday, August 7
14:00 - 23:59 Check-in begins (Front desk at your assigned hotel)
19:30 - 22:00 Dinner (Restaurant Hotel Hacienda Los Laureles)
20:30 - 21:30 Informal gathering
A welcome drink will be served at the hotel.
(Hotel Hacienda Los Laureles)
Monday, August 8
07:30 - 08:45 Breakfast (Restaurant at your assigned hotel)
08:45 - 09:00 Introduction and welcome (Conference Room San Felipe)
09:00 - 09:45 Falai Chen: Implicitization using moving planes and moving quadrics
In this talk, I will first review some recent work on constructing moving quadrics from moving planes that follow a tensor product surface with no base points, assuming that there are no moving planes of low degree following the surface. The I will discuss the possibility of extending the results to more general cases.
(Conference Room San Felipe)
09:45 - 10:30 Xuhui Wang: Complex, Hyperbolic and Parabolic Rational Curves
This talk is a sequel to the talk we presented on Complex Rational Curves at the Banff Conference on Algebraic Geometry and Geometric Modeling in January 2013. Here we show how to extend many of the good properties of complex rational curves including low degree, fast algorithms for computing 𝜇-bases, special implicit form and easy detection to hyperbolic and parabolic rational curves. Just like complex rational curves are generated by using complex coefficients to construct real rational curves, hyperbolic and parabolic rational curves use hyperbolic and parabolic (dual real) numbers to construct real rational curves. We review the algebra of hyperbolic and parabolic numbers and we show how to apply this algebra to construct real rational curves with nice properties. Examples will be provided to flesh out the theory.
(Conference Room San Felipe)
10:30 - 11:00 Coffee Break (Conference Room San Felipe)
11:00 - 11:45 Shen Liyong: Exact µ-bases for Rational Tensor Product Surfaces
We investigate conditions under which the resultant of a µ-basis for a rational tensor product surface is the implicit equation of the surface without any extraneous factors. We provide algorithms for computing such special µ-bases without computing the base points explicitly, and we show how these exceptional µ-bases are related to the number of base points counting multiplicity of the corresponding surfaces.
(Conference Room San Felipe)
11:45 - 12:30 Ron Goldman: Algebraic surfaces of revolution and algebraic surfaces invariant under scissor shears: similarities and differences
Scissor shears are space transformations sharing certain properties with rotations in 3-space. In fact, the formulas for scissor shears are, up to sign, the same as the formulas for rotations with sines and cosines replaced by hyperbolic sines and hyperbolic cosines. Thus one might consider scissor shears as hyperbolic versions of 3D rotations. While algebraic surfaces of revolution, which are well-known in Computer Aided Geometric Design, are algebraic surfaces invariant under all the rotations about a fixed axis (the axis of revolution of the surface), algebraic scissor shear invariant surfaces (or SSI for short) are invariant under all the scissor shear transformations about a fixed axis. Hence, both types of surfaces can be constructed from an axis, and an algebraic space curve.
Interestingly, there are a number of analogies, but also differences, between these two types of surfaces. In both cases, the intersections of the surface with a plane normal to the axis are curves of the same nature, circles in the case of surfaces of revolution, and hyperbolas in the case of ssi surfaces. While surfaces of revolution can have either one axis or infinitely many axes (when the surface is a union of spheres), ssi surfaces can have one, three, or infinitely many axes (when the surface is the union of hyperboloids of one sheet and cones with the same axis, or the union of hyperboloids of two sheets and cones with the same axis). Furthermore, in both cases the form of highest degree of the implicit equation of the surface has a special structure, where again circles are replaced by hyperbolas in the case of ssi surfaces. Finally, the axis (or axes) can be detected by similar methods in both cases: factoring the form of highest degree, and ontracting the tensor corresponding to the highest degree form.
References:
[1] Alcazar J.G., Goldman R., (2016), Finding the axis of revolution of a surface of revolution, to appear in IEEE Transactions in Visualization and Computer Graphics.
[2] Alcazar J.G., Goldman R., (2016), Algebraic surfaces invariant under scissor shears, submitted.
(Conference Room San Felipe)
12:30 - 14:30 Lunch (Restaurant Hotel Hacienda Los Laureles)
14:30 - 15:15 Tom Sederberg: An Inverse Eigenvalue Problem for Subdivision Surfaces
A longstanding problem for non-uniform Catmull-Clark surfaces involves finding a refinement matrix for which the second and third eigenvalues are the same. If this problem is approached algebraically, the solution is nearly hopeless. I will present a geometric insight which unlocks an astonishingly simple solution.
(Conference Room San Felipe)
15:15 - 16:00 Carlos D'Andrea: On minimal generators of the ideal of moving curves following a rational plane parametrization
Recently, J. Madsen (Equations of Rees algebras of ideals in two variables) has obtained a description of the bidegrees of a partial subset of minimal generators of the ideal of moving curves following a rational plane parametrization. In a joint project with Teresa Cortadellas and David Cox, we are working out the explicit form of these generators as well as an explanation of their existence based on a factorization of the input parametrization via a lifting of the curve to a larger projective space of dimension $\mu$.
(Conference Room San Felipe)
16:00 - 16:30 Coffee Break (Conference Room San Felipe)
16:30 - 17:15 Laurent Buse: Syzygies and distance functions to parameterized curves and surfaces
Given a parameterized plane curve, space curve or surface, several methods using syzygies of the coordinates of such parameterizations have been developed to describe and analyze their images, a typical example being the implicitization problem. In this talk, we will explain and illustrate how syzygies can also be used to reveal distances to parameterized curves and surfaces.
This is a joint project with N. Botbol and M. Chardin.
(Conference Room San Felipe)
19:00 - 21:00 Dinner (Restaurant Hotel Hacienda Los Laureles)
Tuesday, August 9
07:30 - 09:00 Breakfast (Restaurant at your assigned hotel)
09:00 - 09:45 Josef Schicho: How to Count Euclidean Embeddings of Rigid Graphs
For a fixed rigid graph, Euclidean embeddings can be considered as solutions of a system of algebraic equations with parameters (the lengths of the edges). The number of complex solutions does not depend on the parameters, as long as they are chosen generically. We present an algorithm for computing this number.
(Conference Room San Felipe)
09:45 - 10:30 Chandrajit Bajaj: Algebra and Geometry of Reproducing Hilbert Space Kernels (Conference Room San Felipe)
10:30 - 11:00 Coffee Break (Conference Room San Felipe)
11:00 - 11:45 Andre Galligo: Extraction of cylinders, cones and tori, from minimal point sets
Extracting geometric primitives from 3D point clouds, relying on a RANSAC approach, is an important problem in reverse engineering. Inspired by effective methods in Algebraic Geometry, we propose new algorithms for extracting cylinders, cones and tori from minimal point sets including oriented points. We emphasize that we do not estimate these geometric primitives from an overdetermined number of conditions, since our aim is improving speed and numerical accuracy. This is a joint work with Laurent Busé.
(Conference Room San Felipe)
11:45 - 12:30 Bert Juettler: Interpolation by Low Rank Spline Surfaces
It has been observed recently that tensor-product spline surfaces with low rank coefficients provide advantages for efficient numerical integration, which is important in the context of matrix assembly in isogeometric analysis. By exploiting the low-rank structure one may efficiently perform multivariate integration by a executing a sequence of univariate quadrature operations. This fact has motivated us to study the problem of creating such surfaces from given boundary curves. On the one hand, we reconsider the classical constructions, which include Coons surfaces. We analyze the rank of the resulting parameterizations. On the other hand, we propose a new coordinate-wise rank-2 interpolation algorithm and discuss its extension to the case of parametric boundary curves. Here we discuss the properties of the new construction, which include a permanence principle and the reproduction of bilinear surfaces. Special attention is paid to the property of affine invariance. This is joint work with Dominik Mokri$\v{s}$.
(Conference Room San Felipe)
12:30 - 14:30 Lunch (Restaurant Hotel Hacienda Los Laureles)
14:30 - 15:15 Alexandra Seceleanu: A hands-on approach to tensor product surfaces of bidegree (2,1)
A central problem in geometric modeling is to find the implicit equations for a curve or surface defined by a regular or rational map. For surfaces the two most common situations are when the surface is given by a map $\mathbb{P}^1\times \mathbb{P}^1 \to \mathbb{P}^3$ or $\mathbb{P}^2 \to \mathbb{P}^3$. The image of regular map $\mathbb{P}^1\times \mathbb{P}^1 \to \mathbb{P}^3$ is called a tensor product surface. We study singularities of tensor product surfaces parametrized by polynomials of bidegree (2, 1) in relation to the syzygies of the ideal generated by these polynomials. We determine all possible numerical types of bigraded minimal free resolutions of such an ideal. This is based on joint work with Hal Schenck and Javid Validashti.
(Conference Room San Felipe)
15:15 - 16:00 Eliana Duarte: Implicitization of tensor product surfaces in the presence of a generic set of base-points
A tensor product surface is the image of a map $\lambda : \mathbb{P}^1\times \mathbb{P}^1 \rightarrow \mathbb{P}^3$, such surfaces arise in geometric modeling and in this context it is important to know their implicit equation. The goal for this talk is to explain how the implicitization problem for tensor product surfaces can be solved using syzygies and illustrate how the geometry of the base locus of $\lambda$ determines the syzygies that are used to compute the implicit equation.
(Conference Room San Felipe)
16:00 - 16:15 Coffee Break (Conference Room San Felipe)
16:30 - 17:15 Nicolas Botbol: Shapes of the simplest minimal free resolutions in $\mathbb P^1\times \mathbb P^1$
In this talk, our goal is to give a detailed description of the (multi)graded minimal free resolution of an ideal $I$ of $R$, generated 3 bihomogeneous polynomials defined by $\mathbf {f} = (f_1, f_2, f_3)$ with bidegree $(d_1, d_2)$, $d_i> 0$ and such that $V (I)$ is empty in $\mathbb{P}^1 \times \mathbb{P}^1$. We will precise the shape of the resolution in degree $d=(1,n)$, and explain how non-genericity (factorization) of the $f_i$'s determine the resolution.
This is a joint work with A. Dickenstein and Hal Schenck.
(Conference Room San Felipe)
19:00 - 21:00 Dinner (Restaurant Hotel Hacienda Los Laureles)
Wednesday, August 10
07:30 - 09:00 Breakfast (Restaurant at your assigned hotel)
09:00 - 13:00 Excursion to Monte Alban (Oaxaca)
13:00 - 14:30 Lunch (Restaurant Hotel Hacienda Los Laureles)
14:30 - 15:15 Amos Ron: Slicing the simplex
Consider the n-D simplex $$\{r\in\mathbb{R}^n_+: \sum_{i=1}^nr(i)\le \sum_{i=1}^n t(i)\},$$ where $r$ is the vector of variables in the ambient space, and $t$ a vector of parameters. Its volume is $$(\sum_{i=1}^nt(i))^n/n!$$ which, when expanded, is also the sum of all normalized monomials (in $t$ ) of degree $n$.
The talk addresses the following challenge:
Find linear hyperplanes $H_2(t),\ldots,H_k(t)$, each parameterized by $t$, with $k$ as large as possible with the following two properties:
(1) When $t\in \mathbb{R}^n_+$, the hyperplanes slice the simplex into $2^{k-1}$ polytopes: i.e., when the hyperplanes are added one by one each additional hyperplane slice all the polytopes that were created so far.
(2) The volume of each polytope is also the sum of normalized monomials (so the monomials that make up the volume of the simplex are just partitioned among the polytopes. No monomial is sliced).
Question: what is the maximal possible $k$? That question is actually not addressed in the talk. We, instead, describe a theory for building such hyperplanes and compute the volumes of the polytopes and their faces.
Note that the total number of monomials is slightly smaller than $2^{2n-1}$.
(Conference Room San Felipe)
15:15 - 16:00 Lucia Romani: Pythagorean-Hodograph B-Spline curves
The present talk is concerned with presenting the general concept of Pythagorean-Hodograph (PH) B-Spline curves. In analogy to the well-known PH Bézier curves their arc length permits a closed form representation, and their offset curves are rational B-Spline curves. We present the construction of these PH B-Spline curves for both, open and closed curves, by constructing their knot vector and control points, and we give analytic expressions for the arc length and the offset curves. In the case of open PH B-Spline curves we also derive a computational strategy for efficiently calculating the curve’s control points. We conclude by presenting examples of PH B-Spline curves of low degree, and evoke a practical interpolation problem using these curves. Both, methods from geometric modelling as well as from algebraic geometry are used to obtain the described results.
(Conference Room San Felipe)
16:00 - 16:15 Coffee Break (Conference Room San Felipe)
16:15 - 17:00 Rida Farouki: Rational rotation-minimizing frames on polynomial space curves: recent advances and open problems
Recent developments in the basic theory, algorithms, and applications for curves with rational rotation-minimizing frames (RRMF curves) are reviewed, and placed in the context of the current state-of-the-art by highlighting the many significant open problems that remain. The simplest non-trivial RRMF curves are the quintics, characterized by a scalar condition on the angular velocity of the Euler–Rodrigues frame (ERF). Two different classes of RRMF quintics can be identified. The first class of curves may be characterized by quadratic constraints on the quaternion coefficients of the generating polynomials; by the root structure of those polynomials; or by a certain polynomial divisibility condition. The second class has a strictly algebraic characterization, less well-suited to geometrical construction algorithms. The degree 7 RRMF curves offer more shape freedoms than the quintics, but only one of the four possible classes of these curves has been satisfactorily described. Generalizations of the adapted rotation-minimizing frames, for which the angular velocity has no component along the tangent, to directed and osculating frames (with analogous properties relative to the polar and binormal vectors) are also discussed. Finally, a selection of applications for rotation-minimizing frames are briefly reviewed—including construction of swept surfaces, rigid-body motion planning, 5-axis CNC machining, and camera orientation control.
(Conference Room San Felipe)
17:00 - 17:30 Jorg Peters: Geometric continuity, analysis at irregularities, and subdividal enclosures (Conference Room San Felipe)
19:00 - 21:00 Dinner (Restaurant Hotel Hacienda Los Laureles)
Thursday, August 11
07:30 - 09:00 Breakfast (Restaurant at your assigned hotel)
09:00 - 09:45 Ragni Piene: Algebraic splines and generalized Stanley-Reisner rings
Given a simplicial complex $\Delta\subset \mathbb R^d$, let $C^r_k(\Delta)$ denote the vector space of piecewise polynomial functions (algebraic splines) of degree $\le k$ and smoothness $r$. A major problem is to determine the dimension (and construct bases) of these vector spaces. Pioneering work by Billera, Rose, Schenck, and others gave upper and lower bounds using homological methods. The ring of continuous splines $C^0(\Delta)=C^0_k(\Delta)$ is (essentially) equal to the face ring, or Stanley--Reisner ring, of $\Delta$ and has the property that its geometric realization describes $\Delta$. More precisely, the part of ${\rm Spec}(C^0(\Delta))$ lying in a certain hyperplane and having nonnegative coordinates is equal'' to $\Delta$. Here we shall consider the \emph{generalized Stanley--Reisner rings} $C^r(\Delta):=\oplus_k C^r_k(\Delta)\subset C^0(\Delta)$. We present a conjectural description of ${\rm Spec}(C^r(\Delta))$ generalizing the one for $r=0$. To illustrate the conjecture, some very simple examples will be given.
(Conference Room San Felipe)
09:45 - 10:30 Nelly Villamizar: Geometrically continuous splines on surfaces of arbitrary topology
We study the space of geometrically continuous splines, or piecewise polynomial functions, on topological surfaces. These surfaces consist of a collection of rectangular and triangular patches together with gluing data that identifies pairs of polygonal edges. A spline is said to be G1-geometrically continuous on a topological surface if they are C1-continoous functions across the edges after the composition by a transition map. In the talk we will describe the required compatibility conditions on the transition maps so that the C1-smoothness is achieved, and give a formula for a lower bound on the dimension of the G1 spline space. In particular, we will show that this lower bound gives the exact dimension of the space for a sufficiently large degree of the polynomials pieces. We will also present some examples to illustrate the construction of basis functions for splines of small degree on particular topological surfaces. *This is a joint work with Bernard Mourrain and Raimundas Vidunas.
(Conference Room San Felipe)
10:30 - 11:00 Coffee Break (Conference Room San Felipe)
11:00 - 11:45 Bernard Mourrain: Space of spline functions on general domains
We study the space of piecewise polynomial functions of bounded degree on a general partition. We are interested in dimension computation and basis function constructions. We describe algebraic techniques, which allow to analayze these spaces and illustrate the approach on some examples.
(Conference Room San Felipe)
11:45 - 12:30 Peter Alfeld: Software for the Analysis of Multivariate Splines
I will demonstrate freely available software that I have written for the analysis of spline spaces on triangular or tetrahedral meshes, or T-meshes and their three-dimensional analogs. The software is based on the Bernstein-Bezier form of polynomials.
(Conference Room San Felipe)
12:30 - 14:30 Lunch (Restaurant Hotel Hacienda Los Laureles)
14:30 - 15:15 Wenping Wang: On Configurations Formed by Two Ellipsoids
First the existing work will be reviewed on using algebraic signatures to classify the types of intersection curves of a pair of quadrics in 3D real projective space. Here, the signature is defined in terms of the eigenvalues of the pencil spanned by the quadratic forms of the two quadrics. Then the study is extended to the classification and stratification of the arrangements defined by two ellipsoids in 3D affine space, based on the signature of the two ellipsoids.
(Conference Room San Felipe)
15:15 - 16:00 Xiaohong Jia: Moving planes and moving spheres following dupin cyclides
We provide explicit representations of three moving planes that form a $\mu$-basis for a cyclide in standard position and pose. We also show how to compute $\mu$-bases for cyclides in general position and pose from their implicit equations. The role of moving planes and moving spheres in bridging the implicit and rational parametric representations of the cyclides is described.
(Conference Room San Felipe)
16:00 - 16:30 Coffee Break (Conference Room San Felipe)
16:30 - 17:15 Haohao Wang: Quaternion Surfaces
A rational quaternion surface is a surface generated by two rational space curve via quaternion multiplication. In general, the structure of a minimal free resolution of a rational surface is unknown. The goal of this talk is to construct the minimal free resolution of a rational quaternion surfaces generated by two rational space curves. We will provide the explicit formula for the maps of the free resolutions. The approach we take is to utilize the information of the $\mu$-basis of the generating rational curves, and create the generating set for the first and second syzygies in the free resolution.
(Conference Room San Felipe)
19:00 - 21:00 Dinner (Restaurant Hotel Hacienda Los Laureles)
Friday, August 12
07:30 - 09:00 Breakfast (Restaurant at your assigned hotel)
09:00 - 09:45 Rimvydas Krasauskas: Rational patches on Darboux and isotropic cyclides and their modeling applications - Part I
Darboux and isotropic cyclides in $\mathbb{R} P^3$ are projections of intersections of certain pairs of quadrics in $\mathbb{R} P^4$. Hence they are particular cases of real Del Pezzo surfaces (of degree 4 or less), that are are known to be rational. Low-degree rational patches on these cyclides described in a form convenient for shape manipulations are the most interesting for modeling applications. Let $\mathcal{A} P^1$ be a projective line over two cases of Clifford algebras $\mathcal{A} = Cl(\mathbb{R}^3), Cl(\mathbb{R}^{2,0,1})$, generated by euclidean space $\mathbb{R}^3$ and pseudo-euclidean space $\mathbb{R}^{2,0,1}$ with signature $(++0)$. Our approach is to treat $\mathcal{A} P^1$ as an ambient space and to consider toric Bezier patches in the corresponding homogeneous coordinates. It is proved that such patches of formal degree 2 with standard and non-standard real structures cover almost all cases of real Darboux and isotropic cyclides. The corresponding implicitization and parametrization algorithms are studied. The applications are related to families of circles on surfaces (including generation of 3-webs of circles) in case of Darboux cyclides and blending of Pythagorean-normal surfaces in case of isotropic cyclides.
(Conference Room San Felipe)
09:45 - 10:30 Severinas Zube: Rational patches on Darboux and isotropic cyclides and their modeling applications - Part II
Darboux and isotropic cyclides in $\mathbb{R} P^3$ are projections of intersections of certain pairs of quadrics in $\mathbb{R} P^4$. Hence they are particular cases of real Del Pezzo surfaces (of degree 4 or less), that are are known to be rational. Low-degree rational patches on these cyclides described in a form convenient for shape manipulations are the most interesting for modeling applications. Let $\mathcal{A} P^1$ be a projective line over two cases of Clifford algebras $\mathcal{A} = Cl(\mathbb{R}^3), Cl(\mathbb{R}^{2,0,1})$, generated by euclidean space $\mathbb{R}^3$ and pseudo-euclidean space $\mathbb{R}^{2,0,1}$ with signature $(++0)$. Our approach is to treat $\mathcal{A} P^1$ as an ambient space and to consider toric Bezier patches in the corresponding homogeneous coordinates. It is proved that such patches of formal degree 2 with standard and non-standard real structures cover almost all cases of real Darboux and isotropic cyclides. The corresponding implicitization and parametrization algorithms are studied. The applications are related to families of circles on surfaces (including generation of 3-webs of circles) in case of Darboux cyclides and blending of Pythagorean-normal surfaces in case of isotropic cyclides.
(Conference Room San Felipe)
10:30 - 11:00 Coffee Break (Conference Room San Felipe)
11:00 - 12:30 Free discussions (Conference Room San Felipe)
12:30 - 14:30 Lunch (Restaurant Hotel Hacienda Los Laureles)