DM819: Computational Geometry (10 ECTS)

STADS: 15013701

Level
Master's level course approved as PhD course

Teaching period
The course is offered when needed.

Teacher responsible
Email: kslarsen@imada.sdu.dk

Timetable
Group Type Day Time Classroom Weeks Comment
Common I Tuesday 08-10 IMADA semi 36-41,43-49,51
Common I Tuesday 08-10 U49D 50 KSL
Common I Thursday 14-16 IMADA semi 36
Common I Thursday 14-16 U157 37-41,43
Common I Thursday 14-16 U44 44-51
Show entire timetable
Show personal time table for this course.

Comment:
Ubegrænset deltagerantal.

Prerequisites:
None

Academic preconditions:
The content of DM508 should be known.

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.

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

Subject overview
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
    Meddeles ved kursets start.


Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
Mandatory assignments. (15013712)

Assessment and marking:
Oral exam, Danish 7 mark scale, external examiner (15013702)

Reexam in the same exam period or immediately thereafter. With few students, an internal examiner may be used.



Expected working hours
The teaching method is based on three phase model.
Intro phase: 28 hours
Skills training phase: 28 hours

Educational activities

Language
This course is taught in Danish or English, depending on the lecturer. However, if international students participate, the teaching language will always be English.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.