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