Objectives and outcome
Acquisition of knowledge of geometric algorithms (computational geometry). Upon completion of the
course, students know how to use basic and more complex geometric data structures and algorithms.
They understand and know how to solve geometric problems related to computational geometry,
computer graphics, graphical user interface, computer games and similar applications.
Lectures
Representation of geometric objects. The problem of determining all intersections of n given segments.
The problem of determining the closest pair of points among n points. Convex hull in 2D space (Jarvis,
Graham’s, divide-and-conquer, quick-hull and randomised algorithm, Kronecker-Seidel’s and Chan’s
algorithm). Planar graphs and doubly connected edge lists (DCEL). Intersections semi-plane and linear
programming. Dual plane and connection between convex hull and semi-plane cross section. Convex
hull in 3D space: (gift-wrapping and incremental algorithm). Polygon triangulation. Voronoi diagrams.
Delaunay triangulation. Efficient data structures for range queries. Efficient structures for working with
intervals.
Practical classes
Implementation of algorithms and data structures covered in lectures. Implementation of a doubly
connected edge list (DCEL) structure used to represent the division of planes into connected
subdomains. Implementation of the algorithm for calculating line arrangement. Implementation of various
algorithms for determining the convex hull, an algorithm for triangulation of a simple polygon, an
algorithm for determining the Voronoi diagram for a given set of points, an algorithm for determining the
Delaunay triangulation. Implementation of some data structures: kd-tree, R-tree, interval trees, segment
trees. Design and analysis of algorithms for various problems in the field of geometry using
computational geometry techniques: sweep line technique, incremental algorithms, dual plane and
problem transformation from problems in the primary plane to problems in the dual plane. Using suitable
structures to solve various computer geometry problems.