#
PřF:M7130 Geometric algorithms - Course Information

## M7130 Geometric algorithms

**Faculty of Science**

Autumn 2008

**Extent and Intensity**- 2/0/0. 2 credit(s) (plus 2 credits for an exam). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium).
**Teacher(s)**- doc. RNDr. Martin Čadek, CSc. (lecturer)
**Guaranteed by**- prof. RNDr. Jan Slovák, DrSc.

Department of Mathematics and Statistics - Departments - Faculty of Science **Timetable**- Mon 12:00–13:50 A107
**Course Enrolment Limitations**- The course is also offered to the students of the fields other than those the course is directly associated with.
**fields of study / plans the course is directly associated with**- Applied Informatics (programme FI, N-AP)
- Informatics (programme FI, M-IN)
- Informatics (programme FI, N-IN)
- Mathematics (programme PřF, M-MA)
- Mathematics (programme PřF, N-MA)

**Course objectives**- A survey of computational geometry. We stress is on various paradigms for algorithm design (one-way run, recursive `divide and conquer', sweep, randomized, geometric transformations), on the necessary data structures, on estimates for the worth-case or expected parameters. At the end of this course, students should be able to implement the basic algorithms of computational geometry.
**Syllabus**- 1. Convex hulls 2. Line segment intersections 3. Triangulations 4. Linear programming 5. Range searching 6. Point location 7. Voronoi diagram 8. Duality and arrangements 9. Delaunay triangulations 10. Convex haulls in dimension 3

**Literature**- učební text na www.math.muni.cz/~slovak
- DE BERG, M., M. VAN KREVELD, M. OVERMARS and O. SCHWARZKOPF.
*Computational Geometry*. 1st ed. Berlin: Springer-Verlag, 1997. 365 pp. ISBN 3-540-61270-X. info

**Assessment methods**- Form: lectures. Written exam.
**Language of instruction**- Czech
**Further Comments**- The course is taught annually.
**Teacher's information**- http://www.math.muni.cz/~slovak

- Enrolment Statistics (Autumn 2008, recent)
- Permalink: https://is.muni.cz/course/sci/autumn2008/M7130