# CIS 610, Fall 2003 Advanced Geometric Methods in Computer Science Course Information September 3, 2003

## Coordinates:

Moore 212, TR noon-1:30pm

## Instructor:

Jean H. Gallier, MRE 254, 8-4405, jean@saul

TBA

## Prerequesites:

Basic Knowledge of linear algebra and geometry (talk to me).

## Textbook:

Review in MathSciNet (item 2) MathSciNet

Problem Sets (4 or 5), project, or presentation.

## A Word of Advice :

Expect to be held to high standards, and conversely! In addition to transparencies, I will distribute lecture notes. Please, read the course notes regularly, and start working early on the problems sets. They will be hard! Take pride in your work. Be clear, rigorous, neat, and concise. Preferably, use a good text processor, such as LATEX, to write up your solutions. You are allowed to work in small teams of at most three. We will have special problems sessions, roughly every two weeks, during which we will solve the problems together. Be prepared to present your solutions at the blackboard. I am hard to convince, especially if your use blatantly ``handwaving'' arguments.

## Brief description:

The course should be of interest to anyone who likes geometry.

The purpose of this course is to present some of the advanced geometric methods used in geometric modeling, computer graphics, computer vision, robotics, etc.

This semester (Fall 2003), I plan to cover the following topics:

1. Basics of Affine Geometry (Mostly a review)

Affine spaces, affine combinations (barycenters), affine subspaces, affine independence, affine frames, convex combinations, affine maps, affine groups, a glimpse at affine geometry (Pappus, Desargues), hyperplanes and affine forms, intersection of affine spaces.

2. Convex sets and Polytopes

Basic properties of convex sets, Half spaces determined by hyperplanes, Caratheodory's theorem on convex hulls, Radon's theorem, Helly's theorem. Separation theorems: Hahn-Banach theorem and others. Supporting hyperplanes, Minkowski's theorem. Vertices and Extremal points, Krein and Milman's theorem. Convex hulls (algorithms). Polytopes and polyhedra: H-polytopes and V-polytopes. Cones. The main theorem. Fourier-Motzkin elimination, affine case. Fourier-Motzkin elimination for cones. The Farkas lemma. Recession cone and homogenization. Vertices, faces and facets. The face lattice. Polarity and duality. The representation theorem for polytopes. Simplicial and simple polytopes.

3. Euclidean Geometry and Applications

Inner Products, Euclidean Spaces, Orthogonality, Orthogonal and Orthonormal bases, A glimpse at Fourier Series, Linear Isometries (also called orthogonal transformations), the orthogonal group, orthogonal matrices, the Groups O(n), SO(n), hyperplane reflections and the Cartan-Dieudonne' theorem, rotations and flips, QR-decomposition, Householder matrices and QR-decomposition.

4. Dirichlet-Voronoi diagrams and Delaunay triangulations

Bisector hyperplanes, Dirichlet-Voronoi diagrams, Some Basics of combinatorial topology: Simplicial Complexes, Star and Link of a vertex, Singular Points, Triangulations, The Euler-Poincare' characteristic, Delaunay triangulations, and applications. Constrained Delaunay triangulations.

5. Spectral Theorems

Normal Linear Maps, Self-Adjoint and Other Special Linear Maps, Normal and Other Special Matrices

6. Singular Value Decomposition (SVD) and Polar Form

Polar Form, Singular Value Decomposition (SVD)

7. Applications of Euclidean Geometry

Applications to Least Squares Problems, Lagrange Multipliers

8. Basics of Classical Lie Groups

The Exponential Map, Some Classical Lie Groups, Symmetric and Other Special Matrices, Exponential of Some Complex Matrices, Hermitian and Other Special Matrices, The Lie Group SE(n) and the Lie Algebra se(n), Finale: Lie Groups and Lie Algebras, Applications of Lie Groups and Lie Algebras

### Geometry (General):

Ge'ome'trie 1, English edition: Geometry 1, Berger, Marcel, Universitext, Springer Verlag, 1990

Ge'ome'trie 2, English edition: Geometry 2, Berger, Marcel, Universitext, Springer Verlag, 1990

Metric Affine Geometry, Snapper, Ernst and Troyer Robert J., Dover, 1989, First Edition

A vector space approach to geometry, Hausner, Melvin, Dover, 1998

Geometry, Audin, Michele, Universitext, Springer, 2002

Geometry, A comprehensive course, Pedoe, Dan, Dover, 1988, First Edition

Introduction to Geometry, Coxeter, H.S.M. , Wiley, 1989, Second edition

Geometry And The Immagination, Hilbert, D. and Cohn-Vossen, S., AMS Chelsea, 1932

Methodes Modernes en Geometrie, Fresnel, Jean , Hermann, 1996

Computational Line Geometry, Pottman, H. and Wallner, J., Springer, 2001

Topological Geometry, Porteous, I.R., Cambridge University Press, 1981

### Convexity:

A course in convexity, Barvinok, Alexander, AMS, (GSM Vol. 54), 2002

Lectures on Polytopes, Gunter Ziegler, Springer (GTM No. 152), 1997

Convex Polytopes, Branko Grunbaum, Springer (GTM No. 221), 2003, Second Edition

Polyhedra, Peter Cromwell, Cambridge University Press, 1999

Convex Sets, Valentine, Frederick, McGraw-Hill, 1964

Convex Analysis, Rockafellar, Tyrrell, Princeton University Press, 1970

### Computational Geometry (Voronoi diagrams, Delaunay triangulations):

Geometry and Topology for Mesh Generation, Edelsbrunner, Herbert, Cambdridge U. Press, 2001

Algorithmic Geometry, Boissonnat, Jean-Daniel and Yvinnec, Mariette (Bronniman, H., translator), Cambridge U. Press, 2001

Computational Geometry in C, O'Rourke, Joseph, Cambridge University Press, 1998, Second Edition

### Lie Groups:

Lie groups, Lie algebras, and representations, Hall, Brian, Springer (GTM No. 222)

Lie Groups. An introduction through linear Linear groups, Wulf Rossmann, Oxford Science Publications, 2002

### Applied Math, Numerical Linear Algebra:

Introduction to Applied Mathematics, Strang, Gilbert, Wellesley Cambridge Press, 1986, First Edition

Linear Algebra and its Applications, Strang, Gilbert, Saunders HBJ, 1988, Third Edition

Applied Numerical Linear Algebra, Demmel, James, SIAM, 1997

Numerical Linear Algebra, L. Trefethen and D. Bau, SIAM, 1997

Matrix Analysis, R. Horn and C. Johnson, Cambridge University Press, 1985

Matrix Computations, G. Golub and C. Van Loan, Johns Hopkins U. Press, 1996, Third Edition

### Differential Geometry:

Differential Geometry of Curves and Surfaces, do Carmo, Manfredo P., Prentice Hall, 1976

Modern Differential Geometry of Curves and Surfaces, Gray, A., CRC Press, 1997, Second Edition

## Geometry And Music

In mathematics, and especially in geometry, beautiful proofs have a certain ``music.'' I will play short (less than 2mn) pieces of classical music, or Jazz, whenever deemed appropriate by you and me!

## Some Slides and Notes

Topics vary from year to year, and are selected among the following subjects (nonexhaustive list):

1. Basics of Affine Geometry

Affine spaces, affine combinations (barycenters), affine subspaces, affine independence, affine frames, convex combinations, affine maps, affine groups, a glimpse at affine geometry (Pappus, Desargues), hyperplanes and affine forms, intersection of affine spaces, basic properties of convex sets, half spaces determined by hyperplanes, Caratheodory's theorem on convex hulls, Radon's theorem, Helly's theorem.

2. Euclidean Geometry and Applications

Inner Products, Euclidean Spaces, Orthogonality, Orthogonal and Orthonormal bases, A glimpse at Fourier Series, Linear Isometries (also called Orthogonal Transformations), the Orthogonal Group, Orthogonal Matrices, the Groups O(n), SO(n), hyperplane reflections and the Cartan-Dieudonne' theorem, rotations and flips, QR-decomposition, Householder matrices and QR-decomposition, Affine Isometries, the Groups Is(n), SE(n), fixed points, the Cartan-Dieudonne' theorem for rigid motions, flips, Orientations of a Euclidean Space, Angles, Volume Forms, Cross-Products. The Algebra H of Quaternions and the Spaces S^3, SU(2), SO(3), and RP^3, quaternion interpolation

3. Dirichlet-Voronoi diagrams, Delaunay triangulations, and applications

4. Hermitian Geometry and Applications

Hermitian Geometry (Sesquilinear Forms, Hermitian Forms, Hermitian Spaces, Pre-Hilbert Spaces, Isometries, Unitary Maps, the Groups U(n), SU(n), Hermitian, reflections, the Cartan-Dieudonne' Theorem, Rotations, flips, Affine isometries, The Groups Is(n, C), SE(n, C), the Cartan-Dieudonne' Theorem, Rotations, flips

A glimpse at Hilbert Spaces

5. Spectral Theorems in Euclidean and Hermitian Spaces, Normal Forms for Linear Maps (SVD, Polar Form), and Applications

Positive definite matrices, Minimization of a positive definite quadratic form with constraints, Lagrange multipliers, Least Squares Estimation, Equilibrium Equations, Weighted Least Squares, Covariant Matrices, More on convex sets (Kalman filters?).

6. Basics of Classical Lie Groups: The Exponential Map, Linear Lie Groups and Lie Algebras

7. Introduction to projective geometry.

This includes projective spaces and subspaces, frames, projective maps, multiprojectve maps, the projective completion of an affine space, cross-ratios, duality, and the complexification of a real projective space.

8. Applications to Rational curves and surfaces. Control points for Rational curves. Rectangular and Triangular rational patches. Drawing closed rational curves and surfaces.

9. Differential geometry of curves

Curvature, torsion, osculating planes, the Frenet frame, osculating circles, osculating spheres.

10. Differential geometry of surfaces

First fundamental form, normal curvature, second fundamental form, geodesic curvature, Christoffel symbols, principal curvatures, Gaussian curvature, mean curvature, the Gauss map and its derivative dN, the Dupin indicatrix, the Theorema Egregium, equations of Codazzi-Mainardi, Bonnet's theorem, lines of curvatures, geodesic torsion, asymptotic lines, geodesic lines, local Gauss-Bonnet theorem.

Other possible topics include:

Calculus of variations (applied to robotics, vision, computer graphics)
Fourier analysis and Wavelets and their applications to image analysis and computer graphics
Optimization methods
Matrix analysis methods, Numerical methods for solving ODE's, PDE's,
Finite elements method.

The table of contents of my book can be found by clicking there: