Segment intersections. Sweep-line algorithms.

Polygons and triangulations of polygons.

Convex sets. Algorithms to construct the convex hull of points in the plane.

DCEL. Point location problem.

Voronoi digrams. Fortune's algorithm.

Delaunay triangulation.

Data structures for points.

Duality and arrangements.

# Computational geometry

M. de Berg, O. Cheong, M. van Kreveld, M. Overmars, Computational Geometry: Algorithms and Applications, 3. izdaja, Springer, 2008.

S. Devadoss, J. O’Rourke, Discrete and Computational Geometry, Princeton University Press, 2011.

J. O’Rourke, Computational Geometry in C, 2. izdaja, Cambridge University Press, 1998.

Students build their knowledge of data structures and basic algorithms used for solving geometric and related problems.

Basic geometric objects

Computing with geometric data

Basic data structures for geometric data

Basic algorithms in Computational Geometry.

Lectures, seminar, exercises, homework, consultations, and independent work by the students.

Type (examination, oral, coursework, project):

Continuous assessment (homework, midterm exams, project work)

Final (written or oral exam)

Grading: 6-10 pass, 5 fail (according to the rules of University of Ljubljana)

CABELLO, Sergio, KNAUER, Christian. Algorithms for graphs of bounded treewidth via orthogonal range searching. Computational geometry, ISSN 0925-7721. [Print ed.], 2009, vol. 42, iss. 9, str. 815-824. [COBISS-SI-ID 15160409]

BERG, Mark de, CABELLO, Sergio, HAR-PELED, Sariel. Covering many or few points with unit disks. Theory of computing systems, ISSN 1432-4350, 2009, vol. 45, no. 3, str. 446-469. [COBISS-SI-ID 14900825]

CABELLO, Sergio, GIANNOPOULOS, Panos, KNAUER, Christian, ROTE, Günter. Matching point sets with respect to the Earth Mover's Distance. Computational geometry, ISSN 0925-7721. [Print ed.], 2008, vol. 39, iss. 2, str. 118-133. [COBISS-SI-ID 14450521]