Courses – Fakultet tehničkih nauka u Novom Sadu

Subject: Combinatorial and geometry algorithms (17.D0M32Z)

Native organizations units: No data

Type of studies	Title
Doctoral Academic Studies	Mathematics in Engineering (Godina: 1, Winter)
Doctoral Academic Studies	Mathematics in Engineering (Godina: 2, Winter)

General information:

Category	Scientific-professional
Scientific or art field	Teorijska i primenjena matematika
Interdisciplinary	Yes
ECTS	10

Educational goal:

Introduction of advanced topics in theory of geometric algorithms, as well as their application to solving standard geometric problems

Educational outcome:

Upon completion of the course, the student should master the basic concepts of storing the geometric objects using proper data structures, as well as efficient algorithms used for manipulation of geometric objects. Also, the student should be capable of modifying the existing algorithms to fit the need.

Course content:

Data structures for storing geometric objects. Deterministic methods for manipulation of point sets, Divide-and-conquer, sweeping. Closest pair, furthest pair. Random sample methods. Sample theorem, moment theorem. Probabilistic algorithms, online algorithms, dynamic algorithms. Convex hull, polytopes. Various incremental algorithms for finding the convex hull of a set of points. Convex hull in 2 dimensions, relation to array sorting. Convex hull of a set of balls. Smallest enclosing ball containing given points. Triangulations in 2 dimensions, with or without restrictions. Delaunay triangulation, triangulations in 3 dimensions. Simplices and complexes. Art gallery problems. Binary space partitions. Painter’s algorithm. Quadtrees and octrees. Hyperplane arrangements, discrepancy. Zone Theorem. Line arrangements in the plane, duality, and arrangements of segments in the plane.

Teaching methods:

Lectures, with active participation of the students, discussion, etc. A student is supposed to write a seminar paper.

Literature:

Authors	Title	Year	Publisher	Language
De Berg, M. et al.	Computational Geometry: Algorithms and Applications	2008	Springer, Berlin	English
Jiri Matousek	Lectures on Discrete Geometry	2002	Springer	English