Computational Geometry (CG)
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 in relation to the problems of for
example molecular biology. 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 ECTS) 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.
MSc Programme in Computer Science
MSc Programme in Bioinformatics
- 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.
Lectures, group work and presentations.
See Absalon when the course is set up.
Bachelor's level course in algorithms and data structures or
Academic qualifications equivalent to a BSc degree is recommended.
PhD’s can register for MSc-course by following the same procedure as credit-students, see link above.
- 7,5 ECTS
- Type of assessment
Oral examination, 20 minutes
- Type of assessment details
- The oral examination is without preparation.
- All aids allowed
- Marking scale
- 7-point grading scale
- Censorship form
- No external censorship
Several internal examiners
Criteria for exam assessment
See Learning Outcome.
Single subject courses (day)
- Theory exercises
- Course number
- 7,5 ECTS
- Programme level
- Full Degree Master
- Block 3
- No limit
The number of seats may be reduced in the late registration period
- Study Board of Mathematics and Computer Science
- Department of Computer Science
- Faculty of Science
- Pawel Winter (5-726379676e42666b306d7730666d)
Mikkel Abrahamsen, Pawel Winter
Are you BA- or KA-student?
Courseinformation of students