Computational Geometry - NDMI097

• Title: Výpočetní geometrie
• Guaranteed by: Department of Applied Mathematics (32-KAM)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2020
• Semester: summer
• E-Credits: 5
• Hours per week, examination: summer s.:2/2, C+Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: not taught
• Language: Czech
• Teaching methods: full-time
• Guarantor: prof. RNDr. Martin Tancer, Ph.D.

Annotation

English

The primary goal of computational geometry is the construction of algorithms and data structures for solving problems stated in terms of basic geometric objects, such as points, lines, polygons, convex polytopes and others. A lot of emphasis is given on the best possible asymptotic comlexity of the algorithms. The main application areas include computer graphics and data visualisation, computer vision, design of 3D objects and robotics. Knowledge in the scope of the course "Introduction to Combinatorial and Computational Geometry" is assumed.

Last update: Töpfer Pavel, doc. RNDr., CSc. (29.01.2018)

Czech

Hlavním cílem výpočetní geometrie je konstrukce algoritmů a datových struktur pro řešení problémů týkajících se základních geometrických objektů (bodů, přímek, polygonů, konvexních mnohostěnů apod.). Velký důraz je kladen na co nejlepší asymptotickou složitost algoritmů. Hlavními oblastmi aplikací jsou počítačová grafika a vizualizace dat, počítačové vidění, design 3D objektů či robotika. Předpokládají se znalosti v rozsahu předmětu "Základy kombinatorické a výpočetní geometrie".

Last update: Töpfer Pavel, doc. RNDr., CSc. (29.01.2018)

Literature

English

• Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars, Computational geometry: Algorithms and applications, Third edition, Springer-Verlag, Berlin, 2008, ISBN: 978-3-540-77973-5. [http://www.cs.uu.nl/geobook/]

• Franco Preparata and Michael Shamos, Computational geometry: An introduction, Texts and Monographs in Computer Science, Springer-Verlag, New York, 1985, ISBN: 0-387-96131-3

Last update: Töpfer Pavel, doc. RNDr., CSc. (29.01.2018)

Syllabus

English

• models of computation (Real RAM)

• convex hull in R^2 and R^3

• triangulation of a polygon

• orthogonal range searching in R^2 and R^d

• point localization and trapezoid decomposition

• construction of the Voronoi diagram and the Delaunay triangulation

• z-buffer, binary space partition, BSP tree

• quadtree

• visibility graph

Last update: Töpfer Pavel, doc. RNDr., CSc. (29.01.2018)

Czech

• modely výpočtu (Real RAM)

• konvexní obal v R^2 a v R^3

• triangulace mnohoúhelníka

• konstrukce arrangementu přímek

• orthogonal range searching v R^2 a v R^d

• lokalizace bodu a lichoběžníkový rozklad

• konstrukce Voroného diagramu a Delaunayovy triangulace

• z-buffer, binární rozklad prostoru, BSP strom

• quadtree

• viditelnostní graf

Last update: Töpfer Pavel, doc. RNDr., CSc. (29.01.2018)