DM819: Computational Geometry (10 ECTS)

STADS: 15006601

Level
Master's level course

Teaching period

Offered when needed

Teacher responsible
Email: kslarsen@imada.sdu.dk

Timetable
There is no timetable available for the chosen semester.

Comment:
Ubegrænset deltagerantal. Kurset kører i 1.+2. kvartal.

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.

Syllabus
See syllabus.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:
Oral exam, Danish 7 mark scale, external examiner
Mandatory assignments, Pass/fail, internal evaluation by teacher

Terms for reexam according to the rules decided by the Study Board. With few students, an internal examiner may be used.

Expected working hours
The teaching method is based on three phase model.

Forelæsninger: 28 timer
Eksaminatorietimer/opgaveregning: 28 timer
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.