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
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
The course is also listed under the following terms Autumn 2007 - for the purpose of the accreditation, Autumn 1999, Autumn 2010 - only for the accreditation, Autumn 2000, Autumn 2001, Autumn 2002, Autumn 2003, Autumn 2004, Autumn 2006, Autumn 2007, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2011 - acreditation, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, autumn 2017, Autumn 2018.
  • Enrolment Statistics (Autumn 2008, recent)
  • Permalink: https://is.muni.cz/course/sci/autumn2008/M7130