SubjectsSubjects(version: 804)
Course, academic year 2017/2018
   Login via CAS
Applied Computational Geometry - NPGR016
Czech 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 2016
Semester: summer
E-Credits: 5
Hours per week, examination: summer s.:2/1 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Additional information:
Note: povolen pro zápis po webu
Guarantor: prof. Ing. Ivana Kolingerová, CSc.
Class: DS, softwarové systémy
Informatika Bc.
Informatika Mgr. - volitelný
Classification: Informatics > Computer Graphics and Geometry
Annotation -
Last update: T_KSVI (22.05.2003)

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.
Literature - Czech
Last update: KOLING (27.04.2005)

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.

Syllabus -
Last update: KOLING (27.04.2005)

1. Introduction, examples of problems solvable by a geometric approach, application areas, fundamental techniques (e.g., divide and conquer, sweeping, locus approach etc.), complexity and evaluation of algorithms, degeneracy and robustness, influence of preprocessing to complexity, programming of geometrically oriented problems in conditions of a limited numerical accuracy

2. Geometric searching - point location, range searching, plane subdivision search, applications

3. Convex hulls - 2D, 3D, on-line problem, approximate solution, applications

4. Voronoi diagrams - properties, construction, applications, dual transformation, generalization

5. Triangulation of point sets in 2D and 3D - Delaunay, greedy, minimum weight triangulation, multicriteria-optimized, data dependent

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

7. Intersection of fundamental geometric objects - line segments, polygons, polyhedra, half-spaces, Boolean operations on polygons

8. Extreme point of a convex polytop

9. Trends, tasks and news in computational geometry

10. On creativity

Charles University | Information system of Charles University |