Program

Please note: MSRI's Summer Graduate Programs are open only to students nominated by MSRI's Academic Sponsor universities. Goals: One of the most useful techniques in Discrete and Computational Geometry is to decompose a region of space (usually a polyhedron) into simplices, that is to say, to triangulate it. When the set of points allowed as vertices is fixed in advance, we say we are triangulating a point configuration, or a point set. On the side of applications, triangulating a geometric domain which we intend to study (whatever its dimension) is a standard procedure for computing its volume, integrating or solving differential equations, interpolation, surface reconstruction from a discrete sampling, fixed-point calculations, etc.. Simplicial or triangulated objects are classical in topology, and they have revived as fundamental techniques in current research due in good part to the availability of tools for effective, concrete computations. In algebraic geometry, the so-called toric varieties and part of elimination theory can be reformulated in terms of polytopes and polyhedra, and there is a quite exact dictionary between algebraic properties of the varieties and properties of special triangulations. The main goal of this school is to introduce graduate students to triangulations of point sets. We plan to stress the rich connections to algebraic geometry, topology, geometric algorithms, and combinatorics. Topics will include the study of topological structures on the set of all triangulations of a point set (flip graphs, secondary polytope, Baues posets), connections of these structures to other fields (computer science, optimization, algebraic geometry). We will discuss many classical examples such as triangulations of cyclic polytopes and cubes. The course will discuss the most recent advances such as the construction of triangulations without bistellar flips, the Generalized Baues Problem, enumeration and optimization problems (e.g. optimal triangulations of cubes). Other themes that will be discussed include: Results indicating how small we can hope our triangulation to be (lower or upper bounds to the sizes of triangulations, for example) Algorithms leading to an optimal triangulation, or a good approximation of it, together with an analysis of how long it will take us to obtain it Theoretical results of how good we can expect the algorithms in the previous paragraph to be. For example, computing the minimal triangulation of a 3-dimensional polytope is NP-complete The problem of enumerating all the possible triangulations of a point set The school will allow students to gain a perspective of cross-disciplinary aspects of the topic from experts and provide them with the opportunity to explore new research topics. Structure: The summer school will have two 90-minute lectures each day in the morning and early afternoon. Late afternoon workshops and laboratories will be based around group explorations of research oriented questions. We also hope to complete each week with a couple of invited lecturers. These will be distinguished experts on special hot topics (to be announced). Students will be expected to have a good background in linear algebra. Knowledge in linear programming and/or computational geometry is useful but is not required. The course will closely follow a draft from a forthcoming book on the topic. This program is partially sponsored by MSRI's Academic Sponsors.       >>>