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

None

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

See itslearning for syllabus lists and additional literature references.

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.

Indicative number of lessons

56 hours per semester

Teaching Method

At the faculty of science, teaching is organized after the three-phase model ie. intro, training and study phase.

Teacher responsible

Name E-mail Department
Kim Skak Larsen kslarsen@imada.sdu.dk Institut for Matematik og Datalogi

Timetable

Odense
Show full time table (start E23)
Show full time table (start F24)

Administrative Unit

Institut for Matematik og Datalogi (datalogi)

Team at Educational Law & Registration

NAT

Offered in

Odense

Recommended course of study

Profile Education Semester Offer period