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
Censorship: 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: Approved - active

Comment

Master level course preapproved as PhD course.

This course is not necessarily offered every year. The regular exam is held in the first-coming exam period immediately after the course has been taught. The first reexam is held in the first-coming reexam period after the regular exam. The second reexam is held in the regular exam period one year after the first regular exam.

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 Blackboard 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

Censorship

Second examiner: External

Grading

7-point grading scale

Identification

Student Identification Card

Language

Normally, the same as teaching language

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, Datalogi

Timetable

Administrative Unit

Institut for Matematik og Datalogi (datalogi, fiktiv)

Team at Registration & Legality

NAT

Recommended course of study

Profile Programme Semester Period