NDAK10009U Computational Geometry (CG)

Volume 2026/2027
Education

MSc Programme in Computer Science

MSc Programme in Bioinformatics

Content

The purpose of this course is to introduce the students to the methods for solving computational problems involving geometric objects. We will look at various problems and study algorithmic paradigms and data structures especially suited to solve geometric problems.

Computational Geometry is concerned with the design and analysis of algorithms and heuristics, exploiting the geometrical aspects of underlying problems (i.e. routing problems, network design, localization problems and intersection problems).
Applications can be found in VLSI-design, pattern recognition, image processing, operations research, statistics and molecular biology.

Learning Outcome

Knowledge in

  • Convex hulls and algorithms to find them.
  • Polygon triangulations and algorithms to find them.
  • Selected range search methods.
  • Selected point location methods.
  • Voronoi diagrams and Delaunay triangulations and algorithms to find them.
  • Selected algorithms for robot motion and visibility problems.
  • Geometric paradigms (e.g. plane sweep, fractional cascading, prune-and-search).

 

Skills to

  • Describe, implement and use selected basic algorithms for solving geometric problems (e.g. convex hulls, localization, searching, visibility graphs).
  • Apply geometric paradigms (e.g. plane sweep, fractional cascading, prune and search) and data structures (e.g. Voronoi diagrams, Delaunay triangulations, visibility graphs) to solve geometric problems.
  • Present a scientific paper where computational geometry plays a crucial role.
  • Read computational geometry papers in scientific journals.

 

Competences to

  • Evaluate which methods are best suited for solving problems involving geometrical properties.

See Absalon when the course is set up.

Bachelor's level course in algorithms and data structures or similar.

Academic qualifications equivalent to a BSc degree is recommended.
Lectures and exercises
  • Category
  • Hours
  • Lectures
  • 20
  • Preparation
  • 120
  • Theory exercises
  • 65
  • Exam
  • 1
  • Total
  • 206
Written
Oral
Individual
Feedback by final exam (In addition to the grade)
Peer feedback (Students give each other feedback)
Credit
7,5 ECTS
Type of assessment
Oral examination, 25 minutes
Type of assessment details
The oral examination is without preparation.
Examination prerequisites

There will be six assignments. To qualify for the exam, the student must obtain at least 50% of the total possible points across all six assignments.

Aid
Only certain aids allowed (see description below)

For each exam topic, the student may bring one brief disposition intended as an outline (not a full text).
The disposition may contain at most 10 lines (e.g., bullet points with single keywords or short sentences) and up to two geometric figures.

Marking scale
7-point grading scale
Censorship form
No external censorship
Several internal examiners
Re-exam

Same as ordinary exam.

To qualify for the re-exam, the student must obtain at least 50% of the total possible points across all six assignments by handing in the assignments no later than three weeks prior to the re-exam date.

Criteria for exam assesment

See Learning Outcome.