Computational geometry 1000-2M00GO
1.Basic geometrical facts.
2.Polygons, cuttings and triangulations.
3.Art gallery problem, visibility graph.
4.Geometrical data structures.
5.Voronoi diagrams and skeletons.
6.Point location in R^2.
7.Dual space, polar sort in R^2.
8. Stabbing problem in R^2 and R^3, Davenport-Schinzel sequences.
9.Linear programming in R^2.
10. Robot motion planning, Minkowski sum.
11. Parallel algorithms.
12. Randomized algorithms.
13. Approximation algorithms.
Type of course
Course coordinators
Learning outcomes
Knowledge
Students:
1. have a knowledge of fundamental branches of mathematics (geometry, combinatorics,
graph theory) that are necessary to study discussed informatics problems (K_W01).
2. have a good understanding of role and meaning of data structures used while solving
the problems (K_W02).
3. are aware of problems, know methods and instruments occuring in theoretic
and practical considerations (K_W03).
Skills
Students:
1. have ability to construct mathematic reasoning (K_U01).
2. are able to express computational problems in the language of mathematics (K_U02).
3. have ability to design algorithms using known methods (K_U04).
Competences
Students:
1. are aware of limitations of their own knowledge and understand the necessity
of further education, including studying other science branches (K_K01).
2. know how to formulate questions that serve self-understanding
of the given thema (in particular, in contact with non-IT specialist) or finding
missing elements of reasoning (K_K02).
3. understand the necessity of regular reading scientific and popular
journals in order to broaden and deepen their knowledge.
Assessment criteria
Class activity. Test exam.
Bibliography
1. F.P.Preparata, M.I.Shamos, "Computational Geometry. An Introduction"
2.J.O'Rourke, "Computational geometry in C"
3.M.de Berg, M. van Kreveld, M.Overmars, O.Schwarzkopf, "Computational Geometry. Algorithms and Applications"
4.Web page: http://www.mimuw.edu.pl/~kowaluk
Additional information
Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes:
- Bachelor's degree, first cycle programme, Computer Science
- Master's degree, second cycle programme, Computer Science
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: