Computational geometry
General data
Course ID: | 1000-2M00GO |
Erasmus code / ISCED: |
11.303
|
Course title: | Computational geometry |
Name in Polish: | Geometria obliczeniowa |
Organizational unit: | Faculty of Mathematics, Informatics, and Mechanics |
Course groups: |
(in Polish) Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka Elective courses for Computer Science |
ECTS credit allocation (and other scores): |
6.00
|
Language: | English |
Type of course: | elective monographs |
Short description: |
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. |
Full description: |
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. |
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 |
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 methods and assessment criteria: |
Class activity. Test exam. |
Classes in period "Winter semester 2023/24" (past)
Time span: | 2023-10-01 - 2024-01-28 |
Navigate to timetable
MO TU WYK
CW
W TH FR |
Type of class: |
Classes, 30 hours
Lecture, 30 hours
|
|
Coordinators: | Mirosław Kowaluk | |
Group instructors: | Mirosław Kowaluk | |
Students list: | (inaccessible to you) | |
Examination: | Examination |
Classes in period "Winter semester 2024/25" (future)
Time span: | 2024-10-01 - 2025-01-26 |
Navigate to timetable
MO TU W TH FR |
Type of class: |
Classes, 30 hours
Lecture, 30 hours
|
|
Coordinators: | Mirosław Kowaluk | |
Group instructors: | Mirosław Kowaluk | |
Students list: | (inaccessible to you) | |
Examination: | Examination |
Copyright by University of Warsaw.