Schedule for: 16w5115 - Computational Algebra and Geometric Modeling

A welcome drink will be served at the hotel.

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.

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.

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.

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.

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.

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

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.

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.

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

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}\).

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.

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.

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.

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}\).

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.