DM819: Computational Geometry
Study Board of Science
Teaching language: Danish or English depending on the teacher, but English if international students are enrolled
EKA: N340001112, N340001102
Assessment: Second examiner: None, Second examiner: External
Grading: Pass/Fail, 7-point grading scale
Offered in: Odense
Offered in: Autumn
Level: Master
STADS ID (UVA): N340001101
ECTS value: 10
Date of Approval: 30-04-2018
Duration: 1 semester
Version: Archive
Comment
Entry requirements
Academic preconditions
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
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
Prerequisites for participating in the exam a)
Timing
Autumn
Tests
Mandatory assignments
EKA
N340001112
Assessment
Second examiner: None
Grading
Pass/Fail
Identification
Full name and SDU username
Language
Normally, the same as teaching language
Examination aids
To be announced during the course
ECTS value
0
Additional information
The prerequisite examination is a prerequisite for participation in exam element a)
Exam element a)
Timing
January
Prerequisites
| Type | Prerequisite name | Prerequisite course |
|---|---|---|
| Examination part | Prerequisites for participating in the exam a) | N340001101, DM819: Computational Geometry |
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
Examination aids
To be announced during the course
ECTS value
10
Additional information
Reexam in the same exam period or immediately thereafter. With few students, an internal examiner may be used.
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.