CIS 610, Spring 2006

Advanced Geometric Methods in Computer Science

New Syllabus for Spring 2006

This version (Spring 2006) will be devoted mostly to

Affine and Euclidean Geometry, Convexity, Polytopes, Combinatorial Topology, Conforming Delaunay Triangulations and 3D Meshing

One of our main goals will be to build enough foundations to understand some recent work in Generation of Smooth Surfaces from 3D Images, Provably Good Mesh Generation and Conforming Delaunay Tetrahedrization.

In particular, among our ultimate goals, we aim to discuss some work of Marcelo Siqueira:
**   (html)
in particular, his dissertation:
**   (pdf)

Course Information
April 5 2006

Coordinates:

Towne 321, M,W, 10:30-12.

Instructor:

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

Office Hours: , or TBA

TBA

Prerequesites:

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

Textbook:

There will be no official textbook(s) but I will use material from several sources including my book (abbreviated as GMA)

Grades:

Problem Sets (3 or 4), project(s), 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:

This course covers some basic material on Affine and Euclidean Geometry, Convexity, Polytopesm, Combinatorial Topology, Conforming Delaunay Triangulations, Smooth Surface Generation from Images and 3D Meshing. The treatment will be rigorous but I will try very hard to convey intuitions and to give many examples illustrating all these concepts.

Tentative Syllabus

Next semester (Spring 2006), I intend to cover (1)-(7) below.
  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.
    (Chapter 1-2 of GMA)
  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.
    • Existence of center points
    • Separation theorems: Hahn-Banach theorem and others.
    • Supporting hyperplanes, Minkowski's theorem.
    • The Farkas lemma
    • Vertices and Extremal points, Krein and Milman's theorem.
    • Polytopes and polyhedra: H-polytopes and V-polytopes. Cones. Vertices, faces and facets.
    • Polarity and duality. The main theorem.
    • Fourier-Motzkin elimination, the equivalence of H-polyhedra and V-polyhedra revisited
      We may also discuss applications to the Support Vector Machine Method
    (Chapter 3 of GMA + Notes)
  3. Euclidean Geometry
    • 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)
    (Chapter 6 of GMA)
  4. Introduction to Combinatorial Topology
    • Simplices and simplicial complexes
    • Topology of simplicial complexes, stars, links
    • Pure complexes, triangulations
    • Combinatorial manifolds
    • Manifolds and Surfaces
    • Orientability
    • Shellings of polytopes
    • The Euler-Poincare' formula for polytopes
    • Simplicial and simple polytopes.
    • Dehn-Sommerville equations
    • The upper bound theorem and cyclic polytopes
    • The classification theorem for surfaces
    • The genus of a surface
    • Partitions of unity
    (Notes)
  5. Dirichlet-Voronoi diagrams and Delaunay triangulations
    • Voronoi diagrams
    • Delaunay triangulations
  6. Conforming Delaunay triangulations and 3D meshing
    • Ruppert's algorithm (2D)
  7. Smooth Surface Generation from Images
    • Well-composed images

Additional References:

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

Lectures on Discrete Geometry, Jiri Matousek, Springer, GTM No. 212, 2002

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

Combinatorial Convexity and Algebraic Geometry, Gunter Ewald, Springer (GTM No. 168), 1996

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

An Introduction to Lie Groups and the Geometry of Homogeneous Spaces, Arvanitoyeogos, Andreas, AMS, SML, Vol. 22, 2003

Lectures on Lie Groups and Lie Algebras, Carter, Roger and Segal, Graeme and Macdonald, Ian, Cambridge University Press, 1995

Lie Groups, Duistermaat, J.J. and Kolk, J.A.C., Springer Verlag, Universitext, 2000

Lie Groups Beyond an Introduction, Knapp, Anthony W., Birkhauser, Progress in Mathematics, Vol. 140, Second Edition, 2002

Theory of Lie Groups I, Chevalley, Claude, Princeton University Press, first edition, Eighth printing, Princeton Mathematical Series, No. 8, 1946

Foundations of Differentiable Manifolds and Lie Groups, Warner, Frank, Springer Verlag, GTM No. 94, 1983

Introduction to Lie Groups and Lie Algebras, Sagle, Arthur A. and Walde, Ralph E., Academic Press, 1973

Representation of Compact Lie Groups, Br\"ocker, T. and tom Dieck, T., Springer Verlag, GTM, Vol. 98, 1985

Elements of Mathematics. Lie Groups and Lie Algebras, Chapters 1--3, Bourbaki, Nicolas, Springer, 1989

Introduction a la Theorie des Groupes de Lie Classiques, Mneimne', R. and Testard, F., Hermann, 1997

Manifolds and Differential Geometry:

Differential Geometry. Curves, Surfaces, Manifolds, Wolfgang Kuhnel, AMS, SML, Vol. 16, 2002

Riemannian Geometry, Do Carmo, Manfredo, Birkhauser, 1992.

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

Riemannian Geometry. A beginner's guide, Frank Morgan, A.K. Peters, 1998, Second Edition

A Panoramic View of Riemannian Geometry, Marcel Berger, Springer, 2003, First Edition.

Geometry of Differential Forms, Shigeyuki Morita, AMS, Translations of Mathematical Monographs, Vol. 201, First, Edition.

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

Applied Math, Numerical Linear Algebra:

Introduction to the Mathematics of Medical Imaging, Charles L. Epstein, Prentice Hall, 2004

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

Matrices, Theory and Applications, Denis Serre, Springer, 2002

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

Introduction to Matrix Analysis , Richard Bellman, SIAM Classics in Applied Mathematics, 1995

Matrix Computations, G. Golub and C. Van Loan, Johns Hopkins U. Press, 1996, Third 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

Papers, Surveys and Talks of Interest

Papers or Surveys Suitable for a Project

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

Back to Gallier Homepage

published by:

Jean Gallier