|
Lecturer(s)
|
-
Vejmělková Ivana, Prof. Dr. Ing.
|
|
Course content
|
1. Examples of solved problems, application areas, degeneracy and robustness, complexity and evaluation of algorithms, fundamental techniques, geometric predicates 2.-3. Geometric location - point location, range search, applications 4. Convex hulls - 2D, 3D, on-line problem, applications 5.-6. Voronoi diagrams - properties, construction, applications, dualization, less usual types of Voronoi diagrams 7.-8. Triangulations in 2D - Delaunay, greedy, MWT, DDT, multicrietria-optimized, constrained triangulations, applications 9. Triangulations in 3D - complications against 2D, properties, applications, Delaunay 3D triangulation 10. Triangulation and partition of polygons, art gallery problem 11. Intersections of basical geometric shapes - lines, polygons 12. Motion planning for robots - a point robot movement, a disk, convex polygon and ledder translation in 2D 13. Other interesting geometric algorithms and data structures, trends and news in computational geometry
|
|
Learning activities and teaching methods
|
Interactive lecture, Project-based instruction, Multimedia supported teaching, Students' portfolio, Seminar classes, Individual study, Students' self-study
- Contact hours
- 52 hours per semester
- Individual project (40)
- 40 hours per semester
- Presentation preparation (report) (1-10)
- 5 hours per semester
- Preparation for an examination (30-60)
- 35 hours per semester
|
| prerequisite |
|---|
| Knowledge |
|---|
| Knowledge of algorithmics and programming at least on the level of the KIV/PPA2 course and knowledge of English at least on the level enabling to read articles in English are expected. |
| learning outcomes |
|---|
| Knowledge of fundamental problems and their typical solutions in the area of applied computational geometry, ability to develop a suitable original solution. The graduate of the course should be able to choose or develop an algorithm suitable for the given problem and to be able to estimate how the given algorithm will behave in real life. |
| teaching methods |
|---|
| Interactive lecture |
| Multimedia supported teaching |
| Project-based instruction |
| Self-study of literature |
| Individual study |
| Students' portfolio |
| Seminar classes |
| assessment methods |
|---|
| Combined exam |
| Portfolio |
| Seminar work |
| Project |
| Individual presentation at a seminar |
|
Recommended literature
|
-
De Berg, Mark. Computational geometry : algorithms and applications. 2., rev. ed. Berlin : Springer, 2000. ISBN 3-540-65620-0.
-
O'Rourke, Joseph. Computational geometry in C. 2nd ed. Cambridge : Cambridge University Press, 1998. ISBN 0-521-64976-5.
|