Babes-Bolyai University of Cluj-Napoca
Faculty of Mathematics and Computer Science
Study Cycle: Graduate
SUBJECT
| MMG0008 | Discrete Geometry |
| Teaching Staff in Charge |
Assoc.Prof. BLAGA Paul Aurel, Ph.D., pablaga cs.ubbcluj.ro |
| Aims |
|
The aim of the course is to familiarize the students with the main notions and problems of discrete and combinatorial geometry: packing and covering, tilings, arrangements of lines, Helly-type theorems, convex polytopes and polyhedra, a.o. We shall prezent, also, some applications to linear programming, computer graphics or geometric number theory. |
| Content |
|
1. Basic geometric notions
- affine dependence, affine and convex subspaces of the Euclidean plane and space - affine and convex combinations, the convex hull of a set of points 2. Fundamental notions of the geometric number theory (lattice points, Minkowski@s theorem) 3. Convexity - separation theorems - theorems of Radon and Helly - methods for the computation of the convex hull - center of sets and the Borsuk-Ulam theorem 4. Convex polytopes and polyhedra - planar graphs - Euler@s theorem - Voronoi@s diagram - regular and semi-regular polyhedra 5. Arrangements of lines and planes 6. Packings of circles and spheres 7. Tilings 8. Vizibility problems. Art gallery theorems 9. Applications to computer graphics and linear programming |
| References |
|
1.Brass, P., Moser, W., Pach, J.: Research Problems in Discrete Geometry, Springer, 2005
2.Edelsbrunner, H.: Algorithms in Combinatorial Geometry, Springer, 1987 3.Goodman, J., O@Rourke, J.: Handbook of Discrete and Computational Geometry, 2nd edition, CRC Press, 2004 4.Grunbaum, B.: Convex Polytopes, Interscience Publishers, 1967 5.Matousek, J.: Lectures on Discrete Geometry, Springer, 2002 6.Matousek, J.: Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry, Springer, 2003 7.O@Rourke, J.: Art Gallery Theorems and Algorithms, Oxford University Press, 1987 8.Pach, J., Agarwal, P.: Combinatorial Geometry, John Wiley, 1995 9.Robertson, J., Webb, W.: Cake-Cutting Algorithms: Be Fair If You Can, A.K. Peters, 1998 10.Ziegler, G.: Convex Polytopes, Springer, 1998 |
| Assessment |
|
Final exam (70%), activity during the semester (30%) |
| Links: | Syllabus for all subjects Romanian version for this subject Rtf format for this subject |