|
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
- Presentation preparation (report) (1-10)
- 5 hours per semester
- Preparation for an examination (30-60)
- 35 hours per semester
- Contact hours
- 52 hours per semester
- Individual project (40)
- 40 hours per semester
|
| prerequisite |
|---|
| Knowledge |
|---|
| rozumět algoritmům i je sám tvořit |
| vybírat datové struktury vhodné pro řešení zadaného problému |
| aktivně užívat znalosti z analytické geometrie |
| pasivního využívání angličtiny |
| Skills |
|---|
| programovat v nějakém běžném programovacím jazyku (C nebo C++ nebo C# nebo Java nebo Pascal/Delphi) |
| využívat při algoritmizaci běžné datové struktury, jako je pole, strom, fronta, zásobník |
| číst odborný text anglicky |
| Competences |
|---|
| N/A |
| N/A |
| learning outcomes |
|---|
| Knowledge |
|---|
| znalost základních algoritmů a datových struktur obecně využívaných pro úlohy výpočetní geometrie |
| znalost speciálních algoritmů vhodných pro různé konkrétní problémy v oblasti výpočetní geometrie |
| znalost různých datových struktur vhodných pro geometricky formulované úlohy |
| Skills |
|---|
| umí vybrat nebo navrhnout algoritmus a datové struktury pro řešení daného geometricky formulovaného problému |
| umí odhadnout složitost algoritmu nebo ji změřit na základě jeho implementace a testování |
| umí posoudit výhody a nevýhody daného algoritmu |
| umí navržené řešení geometricky formulovaného problému implementovat a otestovat |
| Competences |
|---|
| N/A |
| N/A |
| teaching methods |
|---|
| Knowledge |
|---|
| Interactive lecture |
| Self-study of literature |
| Individual study |
| Students' portfolio |
| Skills |
|---|
| Practicum |
| Project-based instruction |
| Individual study |
| assessment methods |
|---|
| Knowledge |
|---|
| Combined exam |
| Project |
| Skills |
|---|
| Project |
| Individual presentation at a seminar |
| Skills demonstration during practicum |
|
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.
|