Skip to main content

Computational geometry

2026/2027
Programme:
Computer Science and Mathematics, Second Cycle
Year:
1 ali 2 year
Semester:
first or second
Kind:
optional
ECTS:
6
Language:
slovenian, english
Lecturer (contact person):
Hours per week – 1. or 2. semester:
Lectures
2
Seminar
1
Tutorial
2
Lab
0
Prerequisites

There are no prerequisites.
 

Content (Syllabus outline)

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.

Readings
  1. M. de Berg ... [et al.]. Computational geometry : algorithms and applications, 2nd, revised ed., Berlin : Springer, cop. 2000.
  2. S. L. Devadoss, J. O’Rourke: Discrete and computational geometry, Princeton : Princeton University Press, cop. 2011.
  3. J. O’Rourke: Computational geometry in C, 2nd ed., Cambridge : Cambridge University Press, 1998
Objectives and competences

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

Intended learning outcomes

Basic geometric objects
Computing with geometric data
Basic data structures for geometric data
Basic algorithms in Computational Geometry.

Learning and teaching methods

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

Assessment

Continuous assessment (homework, midterm exams, project work)
Final (written or oral exam)
5 - 10, a student passes the exam if he is graded from 6 to 10

Lecturer's references

Sergio Cabello Justo:
– 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]
– 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, 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]