Computational geometry

elective monographs

Analysis of selected problems of computational geometry and methods which solve them (sweep line, divide and conquer, prune and search, duality etc.). Theory and applications.

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.

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

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.

Class activity. Test exam.