Hee-Kap Ahn. Dept. Computer Science and Engineering, POSTECH
Xavier Goaoc. VEGAS project-team, INRIA
Discrete geometry is intimately connected to computational geometry. This course will cover basic concepts of discrete geometry, including convexity, incidence problems, convex polytopes, arrangements of geometric objects, lower envelopes, crossing numbers. In addition, we will study how to design optimal algorithms for geometric problems, by exploiting these combinatorial and geometric properties.
classes : Tue. & Thu. 14:00-15:15 / B2-104
Participation(20%), Homework (20%), Midterm exam. (30%) Final exam. (30%)
Lectures on Discrete Geometry by Jiri Matousek.
Springer Graduate Texts in Mathematics , Vol. 212, 2002, ISBN: 978-0-387-95374-8
More on the textbook at the author's page http://kam.mff.cuni.cz/~matousek/dg.html / Publisher's page http://www.springer.com/math/geometry/book/978-0-387-95374-8
Computational Geometry by Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Cheong.
3rd Edition, Springer, 2008.
We are going to study the following topics in regular classes.
TITLE: Convex polytopes, Linear Programming, and a Counter-Example to the Hirsch Conjecture
DESCRIPTION: In this lecture, we investigate the diameter of convex polytopes, which is the smallest number (in terms of number of edges) that ensures one can travel between any two vertices of a polytope. This quantity is relevant for studying the speed of the famous simplex algorithm for linear programming. We present a completely detailed (and understandable!) proof that the 54-year-old Hirsch Conjecture is false! If time permits, we will discuss avenues of current research regarding new conjectures about the diameters of polytopes. The only prerequisites for this lecture are the very basics about polytopes.
TITLE: Combinatorial Characterizations of Rigidity of Frameworks
DESCRIPTION: The
theory of rigidity/flexibility of frameworks (i.e., so-called truss
structures in structural engineering) has a wide range of applications
in applied geometry, e.g., in molecular conformation problems, in
computer aided design, and in scene analysis. One of the main topics
in this field is to provide a combinatorial characterization of
generic rigidity and to develop an efficient combinatorial algorithm
for calculating the degree-of-freedom based on it. In this talk, I
will give a brief introduction to this topic and also explain a recent
research topic on molecular frameworks.
Final exam : December 1 (Thu), 14:00 - 15:15 at B2-104.
All assignments are due at the beginning of class on the specified date.
homework 1: pdf. due: September 27.