Babes-Bolyai University of Cluj-Napoca
Faculty of Mathematics and Computer Science
Study Cycle: Graduate
SUBJECT

Code	Subject	
MMG0008	Discrete Geometry	

Section	Semester	Hours: C+S+L	Category	Type	
Mathematics - in Romanian	6	2+1+0	speciality	optional	
Applied Mathematics	6	2+1+0	speciality	optional	

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	
Bibliography	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%)