Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2019/2020

Computational Geometry

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
BE4M39VG Z,ZK 6 2P+2S
Předmět nesmí být zapsán současně s:
Výpočetní geometrie (B4M39VG)
Předmět je náhradou za:
Výpočetní geometrie (B4M39VG)
Přednášející:
Petr Felkel (gar.)
Cvičící:
Petr Felkel (gar.)
Předmět zajišťuje:
katedra počítačové grafiky a interakce
Anotace:

The goal of computational geometry is analysis and design of efficient

algorithms for determining properties and relations of geometric

entities. The lecture focuses on geometric search, point location,

convex hull construction for sets of points in d-dimensional space,

searching nearest neighbor points, computing intersection of polygonal

areas, geometry of parallelograms. New directions in algorithmic design. Computational geometry is applied not only in geometric applications, but also in common database searching problems.

Výsledek studentské ankety předmětu je zde: http://www.fel.cvut.cz/anketa/aktualni/courses/AE4M39VG

Požadavky:

Knowledge of Fundamental sorting and searching algorithms. Linear algebra and fundamentals of computer graphics are advantageous

Osnova přednášek:

1. Computational geometry (CG), typical applications, effective algorithm design techniques

2. Fundamentals of geometry, data structures for CG.

3. Geometric searching

4. Geometric searching 2

5. Planar convex hull

6. Convex hull in 3D

7. Proximity problems, Voronoi diagram.

8. Voronoi diagram applications.

9. 2D a 3D triangulations

10. Intersections of line segments

11. Intersections of polygonal areas and halfspaces

12. Geometry of parallelopids.

13. Dual algorithms.

14. New directions in algorithmic design

Osnova cvičení:

1. Introduction to the form of the seminars, Selection of topics for assignment.

2. Individual preparation of the presentations

3. Presentations of the topic assigned, discussion. Evaluation of the presentation materials and evaluation of the speech by classmate students. Ideas for improvements.

4. Presentation of the topic assigned

5. Presentation of the topic assigned

6. Presentation of the topic assigned

7. Presentation of the topic assigned

8. Presentation of the topic assigned

9. Presentation of the topic assigned

10. Presentation of the topic assigned

11. Presentation of the topic assigned

12. Presentation of the topic assigned

13. Assessment

14. Spare

Cíle studia:

The course is an informal continuation of fundamental data structures and algorithms courses. You will learn geometric algorithms and data structures allowing for effective computations, e.g., localization of area hit by a ray, computation of intersections and triangulation. You will train presentation and professional discussion skills on the seminars. All of it should not be missing in knowledge of educated progressive Master of Science.

Studijní materiály:

1. Preperata F.P.- M.I.Shamos: Computational Geometry An Introduction. Berlin, Springer-Verlag,1985.

2. Edelsbrunner H.: Algorithms in Combinatorial Geometry. Berlin, Springer - Verlag, 1987.

3. de Berg, M.,van Kreveld, M., Overmars, M., Schvarzkopf, O.: Computational Geometry, Berlin, Springer, 1997.

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

Poznámka:

https://cw.fel.cvut.cz/wiki/courses/ae4m39vg/start

Další informace:
https://cw.fel.cvut.cz/wiki/courses/ae4m39vg/start
Rozvrh na zimní semestr 2019/2020:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
Út
St
Čt
místnost KN:E-126
Felkel P.
09:15–10:45
(přednášková par. 1)
Karlovo nám.
Trnkova posluchárna K5
místnost KN:E-126
Felkel P.
12:45–14:15
(přednášková par. 1
paralelka 101)

Karlovo nám.
Trnkova posluchárna K5

Rozvrh na letní semestr 2019/2020:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 22. 9. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet4698606.html