Syllabus
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
Annotation
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.