M7130 Geometric algorithms

Faculty of Science
Autumn 2015
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
Supplier department: Department of Mathematics and Statistics – Departments – Faculty of Science
Timetable
Tue 10:00–11:50 M1,01017
Course Enrolment Limitations
The course is also offered to the students of the fields other than those the course is directly associated with.
The capacity limit for the course is 140 student(s).
Current registration and enrolment status: enrolled: 0/140, only registered: 0/140, only registered with preference (fields directly associated with the programme): 0/140
fields of study / plans the course is directly associated with
Course objectives
The aim of the course is to introduce basic algorithms of computational geometry. Passing the course students will know *basic algorithmic methods, *basic data and searching structures and *worst and expected times of the algorithms. *At the end of this course students will 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
Teaching methods
Lectures.
Assessment methods
Written exam. Requirements: to manage the theory from the lecture, to be able to solve connected problems.
Language of instruction
Czech
Further Comments
Study Materials
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 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2011 - acreditation, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2016, autumn 2017, Autumn 2018.
  • Enrolment Statistics (Autumn 2015, recent)
  • Permalink: https://is.muni.cz/course/sci/autumn2015/M7130