M7130 Geometric algorithms

Faculty of Science
Autumn 2007 - for the purpose of the accreditation
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
Contact Person: prof. RNDr. Jan Slovák, DrSc.
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 Geoemtry. We stress the comparison of various paradigms for algorithm design (one-way run, recursive `divide and conquer', sweep, randomized, geometric transformations), the necessary data structures, estimates for the worth-case or expected parameters
Syllabus
  • 1. Convex objects 2. Convex hulls 3. Voronoi diagrams and applications 4. Triangulations and plane divisions 5. Intersections 6. Range searching 7. Iso-orthogonal objects
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 (in Czech)
písemná zkouška zpravidla bez ústní rozpravy
Language of instruction
Czech
Further Comments
The course can also be completed outside the examination period.
The course is taught annually.
The course is taught: every week.
Teacher's information
http://www.math.muni.cz/~slovak
The course is also listed under the following terms Autumn 1999, Autumn 2010 - only for the accreditation, Autumn 2000, Autumn 2001, Autumn 2002, Autumn 2003, Autumn 2004, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2011 - acreditation, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, autumn 2017, Autumn 2018.