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: 07-10-2020
Duration: 1 semester
Version: Archive
Comment
Master level course preapproved as PhD course.
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:
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 the courses DM507 and DM549, together with parts of DM551 and DM553.
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.
The examination form for re-examination may be different from the exam form at the regular exam.
The examination form for re-examination may be different from the exam form at the regular exam.
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.