Kursussøgning, efter- og videreuddannelse – Københavns Universitet

Videresend til en ven Resize Print Bookmark and Share

Kursussøgning, efter- og videreuddannelse

Computational Geometry (CG)

Practical information
Study year 2016/2017
Block 3
Programme level Full Degree Master
Course responsible
  • Pawel Winter (5-726379676e42666b306d7730666d)
  • Department of Computer Science
Course number: NDAK10009U

Course content

The purpose of this course is to introduce the students to the methods  for solving problems where geometrical properties are of particular importance. We will look at some basic problems,  at algorithmic paradigms especially suited to solve such problems, and at geometric data structures. We will also look at the applications of computational geometry to the problems of molecular biology in particular. No a priori knowledge of molecular biology is required. During the course, the students will be asked to make a project proposal (7.5 or 15 ETCS) which they will have the opportunity to work on in the following block).

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


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



  • 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.



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

Recommended prerequisites

Bachelor's level course in algorithms and data structures.

Sign up

As an exchange, guest and credit student - click here!

Continuing Education - click here!


MSc programme in Computer Science
MSc Programme in Bioinformatics


Study Board of Mathematics and Computer Science

Course type

Single subject courses (day)


1 block


---- SKEMA LINK ----

Teaching and learning methods

5 weeks lectures, 2 weeks group work, 2 weeks paper presentations


No limit




See Absalon when the course is set up.


Category Hours
Lectures 20
Colloquia 10
Preparation 115
Theory exercises 60
Exam 1
English 206


Type of assessment

Oral examination, 20 minutes
Oral examination without preparation.


All aids allowed

Marking scale

7-point grading scale

Criteria for exam assessment

In order to achieve the highest grade 12, a student must be able to

  • define the problems introduced during the course
  • explain the algorithms and data structures for solving these problems,
  • explain the geometric paradigms introduced during the course
  • discuss the content of the paper covered by the student's group in the seminar presentation.

Censorship form

No external censorship
Several internal examiners


Same as ordinary exam.

3 out of 6 assignments must be handed in and approved no later than two weeks prior to re-exam date.

Mere information om kurset
Er du BA- eller KA-studerende?
Er du bachelor- eller kandidat-studerende, så find dette kursus i kursusbasen for studerende:

Kursusinformation for indskrevne studerende