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:3012.
Instructor:
Jean H.
Gallier, MRE 476, 84405, 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.

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 12 of GMA)

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:
HahnBanach theorem and others.

Supporting hyperplanes, Minkowski's theorem.

The Farkas lemma

Vertices and Extremal points, Krein and Milman's theorem.

Polytopes and polyhedra: Hpolytopes and Vpolytopes. Cones.
Vertices, faces and facets.

Polarity and duality.
The main theorem.

FourierMotzkin elimination, the equivalence of Hpolyhedra and Vpolyhedra
revisited
We may also discuss applications to the Support Vector Machine Method
(Chapter 3 of GMA + Notes)

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)

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 EulerPoincare' formula for polytopes

Simplicial and simple polytopes.

DehnSommerville equations

The upper bound theorem and cyclic polytopes

The classification theorem for surfaces

The genus of a surface

Partitions of unity
(Notes)

DirichletVoronoi diagrams and Delaunay triangulations

Voronoi diagrams

Delaunay triangulations

Conforming Delaunay triangulations and 3D meshing

Smooth Surface Generation from 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 CohnVossen, 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, McGrawHill, 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, JeanDaniel 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 13,
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
 Preface and Chapter 1 of GMA
(ps)

(pdf)
 Chapter 2 of GMA
(ps)

(pdf)
 Chapter 3 of GMA
(ps)

(pdf)
 Chapter 6 of GMA
(ps)

(pdf)
 Basics on Affine spaces I (slides)
(ps)

(pdf)
 Basics on Affine spaces II, Convex Sets, a first look (slides)
(ps)

(pdf)
 Convex sets: A deeper look (slides)
(ps)

(pdf)
 Euclidean Geometry (GramSchmidt) I (slides)
(ps)

(pdf)
 Euclidean Geometry (Linear isometries, The Groups O(n), SO(n),
QRdecomposition, the CartanDieudonne' Theorem) II (slides)
(ps)

(pdf)
 Euclidean Geometry (Affine isometries, The Groups Is(n), SE(n),
Fixed Points of Affine Isometries, CartanDieudonne', Orientation
of a Euclidean space, Generalized Crossproduct) III (slides)
(ps)

(pdf)
 Polyhedra and Polytopes: A deeper look (slides)
(ps)

(pdf)
 Basics of Combinatorial Topology (slides)
(ps)

(pdf)
 Shellings, The EulerPoincare' formula, DehnSommerville equations,
the Upper Bound Theorem (slides)
(ps)

(pdf)

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
 DirichletVoronoi diagrams and Delaunay triangulations (slides)
(ps)

(pdf)
 Quaternions and Rotation, SO(3), RP^3, SO(4) (slides)
(ps)

(pdf)

Convex sets, Polytopes, Combinatorial Topology, Voronoi Diagrams
and Delaunay Triangulations
(book home page, html)

The Classification Theorem for Compact Surfaces And a Detour on
Fractals
(book home page)
(pdf)
 Manifolds, Part II
(slides, ps)

(slides, pdf)

Notes on Group Actions, Manifolds, Lie Groups and Lie Algebras
(html)

Updates and Corrections for Gunter Ziegler's book
(pdf)
 Lecture Notes on Differentiable Manifolds, Geometry of Surfaces, etc.,
by Nigel Hitchin
(html)
 An Introduction to Riemannian Geometry, by S. Gudmundsson
(html)
 Bibliography (from book)
(ps)

Clifford algebras, Clifford groups, and the groups
Pin and Spin (notes)
(ps)

(pdf)
 ``Semisecret'' Notes on algebraic geometry and algebra
(algebra, html)

(algebraic geometry, html)

(complex algebraic geometry, html)
 Basics of Algebra and Analysis
(html)
Papers, Surveys and Talks of Interest
 Computational Geometry, Lecture 3 (ShangHua Teng)
(ps)
 CS 267 Graph Partitioning (Kathy Yellick)
(pdf)
 Topics in Geometric Combinatorics (Francis E Su)
(pdf)
 Jonathan Shewchuk's Home page
(html)

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 lineartime
(pdf)
 The complexity of finding small triangulations of convex 3polytopes,
by A. Below, J. De Loera and J. RichterGebert
(pdf)

A Delaunay Refinement Algorithm for Quality 2Dimensional 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 gTheorem, 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)
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: