Applied Computational Geometry - NPGR016

• Title: Aplikovaná výpočetní geometrie
• Guaranteed by: Department of Software and Computer Science Education (32-KSVI)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2024
• Semester: summer
• E-Credits: 5
• Hours per week, examination: summer s.:2/1, C+Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: not taught
• Language: Czech, English
• Teaching methods: full-time
• Additional information: http://afrodita.zcu.cz/~kolinger/vyukaUK.html
• Note: enabled for web enrollment
• Guarantor: prof. Dr. Ing. Ivana Kolingerová
• Class: DS, softwarové systémy; Informatika Bc.; Informatika Mgr. - volitelný
• Classification: Informatics > Computer Graphics and Geometry

Annotation

English

The course deals with methods and data structures from the algorithmic computational geometry, usable for geometrically formulated problems in computer graphics and its applications, but also pattern recognition, database systems, artificial intelligence, statistics etc. Examples of solved problems are as follows: geometric search, triangulation, mutual position of geometric objects. Examples of presented methods are as follows: sweeping, duality, divide and conquer, Voronoi diagrams.

Last update: T_KSVI (22.05.2003)

Czech

Předmět se zabývá postupy a datovými strukturami z oblasti algoritmické výpočetní geometrie využitelnými pro řešení geometricky formulovaných úloh především z oblasti počítačové grafiky a jejích aplikací, dále např. rozpoznávání, databázových systémů, umělé inteligence, statistiky i jiných oblastí. Příklady řešených problémů jsou geometrické vyhledávání, triangulace, vzájemná poloha geometrických objektů. Příklady užitých metod jsou zametání, dualita, rozděl a panuj, Voronoiovy (Voroného) diagramy. Cvičení: rozbor algoritmů a návrh nových a prezentace studentských prací.

Last update: T_KSVI (22.05.2003)

Course completion requirements

English

Conditions are given at http://afrodita.zcu.cz/~kolinger/AVG/AVG_e.htm.

Last update: Kolingerová Ivana, prof. Dr. Ing. (21.06.2018)

Czech

Podmínky jsou uvedeny na http://afrodita.zcu.cz/~kolinger/AVG/AVG_c.htm.

Last update: Kolingerová Ivana, prof. Dr. Ing. (21.06.2018)

Literature

English

1. O' Rourke, Joseph: Computational Geometry in C, Cambridge University Press, 1st edition, 1994 or 2nd edition, 2000

2. de Berg, Mark, van Kreveld, Marc, Overmars, Mark, Schwarzkopf, Otfried: Computational Geometry, Algorithms and Applications, Springer Verlag, 1st edition, 1997 or 2nd edition, 2001

3. Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction, Springer-Verlag, New York Berlin Heidelberg Tokyo, 1985

4. PowerPoint presentation files on the course home page and other materials provided by the teacher in the printed form

Last update: Kolingerová Ivana, prof. Dr. Ing. (21.06.2018)

Czech

1. O' Rourke, Joseph: Computational Geometry in C, Cambridge University Press, 1.vydání, 1994 nebo 2.vydání, 2000

2. de Berg, Mark, van Kreveld, Marc, Overmars, Mark, Schwarzkopf, Otfried: Computational Geometry, Algorithms and Applications, Springer Verlag, 1.vydání, 1997 nebo 2.vydání, 2001

3. Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction, Springer-Verlag, New York Berlin Heidelberg Tokyo, 1985

4. Podklady přednášek v PowerPoint poskytnuté vyučujícím a další materiály distribuované na cvičení

Doporučuje se znalost angličtiny na úrovni dovolující studovat anglické prameny.

Last update: Kolingerová Ivana, prof. Dr. Ing. (21.06.2018)

Syllabus

English

1. Computational geometry as a tool for geometric and graphical applications

2. Geometric search - point location, range search

3. Convex hulls in 2D, 3D

4. Voronoi diagrams - properties, construction

5. Voronoi diagrams - generalizations and applications

6. Planar triangulations (Delaunay, greedy, data dependent, constrained, minimum weight, multicriterially optimized) and their applications

7. Tetrahedronizations and their applications

8. Polygon triangulation and decomposition (into trapezoids, convex polygons), art gallery problem

9. Medial axis

10. Surface reconstruction from scattered points

11. Intersections (line segments, polygons, halfplanes, dualities)

12. In case of interest and free time: scientific writing, presentations, creativity

Last update: Kolingerová Ivana, prof. Dr. Ing. (20.06.2018)

Czech

1. Výpočetní geometrie jako nástroj pro geometrické a grafické aplikace

2. Geometrické vyhledávání - lokace bodu, hledání intervalů

3. Konvexní obálky v 2D a 3D

4. Voroného diagramy v 2D a 3D - vlastnosti, konstrukce

5. Aplikace a zobecnění Voroného diagrammů

6. Rovinné triangulace (Delaunayova, greedy, datově závislá, s omezením, s minimální váhou, multikriteriálně optimalizovaná) a jejich aplikace

7. Tetrahedronizace a jejich aplikace

8. Triangulace polygonu, dělení polygonu na konvexní části, na lichoběžníky, teorém obrazové galerie

9. Střední osa

10. Rekonstrukce povrchu z rozptýlených bodů

11. Průsečíky a průniky (úsečky, polygony, poloroviny, dualita)

12. Podle času a zájmu doplňková témata: psaní odborných článků, prezentace, kreativita

Last update: Kolingerová Ivana, prof. Dr. Ing. (20.06.2018)