CIS 610, Fall 2003

Advanced Geometric Methods in Computer Science Course Information September 3, 2003

Coordinates:

Instructor:

Office Hours: , or TBA

Prerequesites:

Textbook:

Springer NY and Amazon.com

Review in MathSciNet (item 2) MathSciNet

Grades:

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

• Latex macros, "mac.tex"
• Latex macros, "mathmac.tex"
• Homework 1 (ps), (pdf), (latex)
• Homework 2 (ps), (pdf), (latex)
• Homework 3 (ps), (pdf), (latex)
• Homework 4 (ps), (pdf), (latex)

A Word of Advice :

Brief description:

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

Additional References:

Geometry (General):

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:

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):

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. An introduction through linear Linear groups, Wulf Rossmann, Oxford Science Publications, 2002

Applied Math, Numerical Linear Algebra:

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:

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

Geometry And Music

Some Slides and Notes

• Questions, Motivations, Problems
• Basics on Affine spaces I (slides)
• Basics on Affine spaces II, Convex Sets, a first look (slides)
• Convex sets: A deeper look (slides)
• Convex sets, Polyhedra and Polytopes: A deeper look (Notes) (ps) (pdf)
• Euclidean Geometry (Gram-Schmidt) I (slides)
• Euclidean Geometry (linear isometries, The Groups O(n), SO(n), QR-decomposition, the Cartan-Dieudonne' theorem) II (slides)
• Euclidean Geometry (linear isometries, QR by Householder matrices, affine isometries, the Groups Is(n), SE(n), fixed points, Cartan-Dieudonne' thm for rigid motions, flips) III (slides)
• Euclidean Geometry (Orientation, angles, volume forms, cross products) IV (slides)
• Euclidean Geometry (Quaternions and rotations in SO(3) and SO(4)) V (slides)
• Polyhedra and Polytopes: A deeper look (slides)

• Zvi Har'el's web site
• The Uniform Polyhedra (web site)
• Polyhedra Collection (Bulatov web site)
• Encyclopedia of Polyhedra (George Hart web site)
• George Hart's web site
• Paper models of polyhedra
• Polyhedra
• Polyhedra Pastimes
• Unfolding Polyhedra
• Tom Getty's Polyhedra

• Voronoi Diagrams (slides)
• Hermitian Spaces (slides)
• Isometries of Hermitian Spaces and Hilbert Spaces (notes)
• Clifford algebras, Clifford groups, and the groups Pin and Spin (notes) (ps) (pdf)
• Spectral Theorems (Symmetric, Skew-Symmetric, Normal matrices) (slides)
• Polar Form and SVD (slides)
• Least squares, Pseudo-inverses, Minimization of quadratic functions using Lagrange multipliers
• Lie Groups and Lie Algebras, the exponential map, part I
• Lie Groups and Lie Algebras, the exponential map, part II
• Notes on Group Actions, Manifolds, Lie Groups and Lie Algebras
• Bibliography (from book))
• Basic Linear Algebra, Determinants

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:

    Table of contents

    For more information, visit
    Geometric Methods and Applications For Computer Science and Engineering

    I will mix assignments not involving programming, and small programming projects. There are plenty of opportunities for trying out the algorithms presented in the course. In particular, it is fairly easy to program many of these algorithms in Mathematica (I have done so, and I'm not such a great programmer!).

    ---

    Back to Gallier Homepage

    published by:

    Jean Gallier