DM819: Computational Geometry
Study Board of Science
Teaching language: Danish or English depending on the teacher, but English if international students are enrolled
EKA: N340001102
Assessment: Second examiner: External
Grading: 7-point grading scale
Offered in: Odense
Offered in: Autumn, Spring
Level: Master's level course approved as PhD course
STADS ID (UVA): N340001101
ECTS value: 10
Date of Approval: 10-04-2024
Duration: 1 semester
Version: Approved - active
Comment
The course is offered as needed and is not necessarily offered every year. Examination tests for DM819 are offered according to the following plan when the course is offered:
- Autumn: ordinary examination (January), first re-examination (March) and 2nd re-examination in (June)
- Spring: ordinary examination (June), first re-examination (August) and 2nd re-examination in (January)
Entry requirements
Academic preconditions
Knowledge of algorithms and data structures and their analysis is assumed, including algorithm design techniques such as divide-and-conquer, balanced binary search trees such as red-black tree, as well as correctness analysis and complexity analysis using recursion equations and asymptotic notation. Further prerequisites includes results on lower bounds for sorting and basic understanding of probability theory. The prerequisites can be obtained through algorithms and discrete mathematics and probability theory courses on a computer science bachelor education.
Course introduction
The course is an introduction to the essential aspects of computational geometry. As an integrated part of the course, the participants should be trained in implementing algorithms from the area. The subject has become an integral part of applications in computer game implementation and computer graphics in general, geographic information systems, robot control, design, image analysis, etc. Since applications in these areas typically involve very large amounts data, there is a demand for very efficient algorithms and search structures for the fundamental problems. Focus will not be on the applications, but on the core problems in computational geometry.
The course builds on competences obtained through algorithms courses in a computer science bachelor degree and gives competences for master thesis work in the area.
With reference to the education's competence profile, the course has focus on
- comprehending a complex problem
- analyzing and working with complex assignments
- working towards solutions, both independently and as part of a team
Expected learning outcome
At the end of the course, the student should be able to:
- explain the functionality and correctness of the covered algorithms and data structures
- analyze the covered algorithms and data structures wrt. time and space complexity
- design efficient algorithms and data structures for variants of the covered problem scenarios
- explain in detail the problems involved in implementing the covered algorithms and data structures in standard programming languages
Content
Line segment intersection, triangulations, linear programming, interval and point location, Voronoi diagrams, convex hull, ray tracing, motion planning, tree-based geometric structures, as well as techniques such as line-sweep, fractional cascading, and randomization, etc.
Literature
Examination regulations
Exam element a)
Timing
If the course is held in the autumn semester, the exam is in January.
If the course is held in the spring semester, the exam is in June.
Tests
Oral exam
EKA
N340001102
Assessment
Second examiner: External
Grading
7-point grading scale
Identification
Student Identification Card
Language
Normally, the same as teaching language
Duration
30 minutes
Examination aids
To be announced during the course
ECTS value
10
Additional information
The exam consists of an oral examination and a project with an overall evaluation.
Indicative number of lessons
Teaching Method
At the faculty of science, teaching is organized after the three-phase model ie. intro, training and study phase.
Intro phase: 28 hours
Training phase: 28 hours (tutorials)
Activities in the study phase:
•Solving problem sets in order to discuss these in the exercise sections.
•Solving the project assignments
•Self-study of various parts of the course material
•Postprocessing of the intro and training sessions
Teacher responsible
Timetable
Administrative Unit
Team at Educational Law & Registration
Offered in
Recommended course of study
Transition rules
Transitional arrangements describe how a course replaces another course when changes are made to the course of study.
If a transitional arrangement has been made for a course, it will be stated in the list.
See transitional arrangements for all courses at the Faculty of Science.