# 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

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)

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
• 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

### 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!

## Papers, Surveys and Talks of Interest

• Computational Geometry, Lecture 3 (Shang-Hua Teng) (ps)
• CS 267 Graph Partitioning (Kathy Yellick) (pdf)
• Topics in Geometric Combinatorics (Francis E Su) (pdf)
• Lecture notes on Delaunay mesh generation, by Jonathan Shewchuk (1999) (pdf)
• Theoretically garanteed Delaunay mesh generation in practice, Short Course, 13th IMR (2004),
by Jonathan Shewchuk (pdf)
• Constrained Delaunay Triangulations ...,
by Jonathan Shewchuk (pdf)
• Voronoi Diagrams, by Franz Aurenhammer and Rolf Klein (1996) (ps)
• Partitioning the permutahedron, by Etienne Rassart (pdf)
• Random Monotone Paths on Polyhedra, by Gunter Ziegler et al (pdf)
• Topological Issues in Hexahedral meshing, by David Eppstein (pdf)
• Visualizing the connection among convex hull, Voronoi diagram and Delaunay triangulation, by John Fisher (pdf)
• Shelling and Ranking (pdf)

## Papers or Surveys Suitable for a Project

• Approximating center points with iterative Radon points (ps)
• A Deterministic Linear Time Algorithm for Geometric Separators and its Applications (ps)
• Regression Depth and Center Points (pdf)
• Computing a centerpoint of a finite planar set of points in linear-time (pdf)
• The complexity of finding small triangulations of convex 3-polytopes, by A. Below, J. De Loera and J. Richter-Gebert (pdf)
• A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation, by Jim Ruppert (pdf)
• When and why Ruppert's algorithm works, by G. Miller, S. Pav and N. Walkington (pdf)
• How good are convex hull algorithms, by D. Avis, D. Bremner and R. Seidel (pdf)
• Convex Hull, Oracles, and Homology, by M. Joswig and G. Ziegler (pdf)
• Algorithms for center and Tverberg points (pdf)
• From Polytopes to Enumeration, by Ed Swartz (pdf)
• Combinatorics with a geometric flavor: some examples, by Gil Kalai (pdf)
• Polytopes Skeletons and Paths, by Gil Kalai (pdf)
• An Introduction to Hyperplane Arrangements, by Richard Stanley (pdf)
• Face Numbers of Polytopes and Complexes, by Louis Bellera and A. Bjorner (pdf)
• The g-Theorem, MA715 Course Notes, by Carl Lee (pdf)
• Triangulations and meshes in computational geometry, by Herbert Edelsbrunner (pdf)
• Computational Topology, by Tamal Dey, Herbert Edelsbrunner and Sumanta Guha (pdf)
• Lectures in Geometric Combinatorics, by Rekha R. Thomas (pdf)
• Triangulations of Point Sets, By J. De Loera, J. Rambau and F. Santos (pdf)