Computational Geometry (CG)
Course content
The purpose of this course is to introduce the students to the
methods for solving computational problems involving geometric
objects. We will look at various problems and study algorithmic
paradigms and data structures especially suited to solve geometric
problems.
Computational Geometry is concerned with the design and analysis of
algorithms and heuristics, exploiting the geometrical aspects of
underlying problems (i.e. routing problems, network design,
localization problems and intersection problems).
Applications can be found in VLSI-design, pattern recognition,
image processing, operations research, statistics and molecular
biology.
MSc Programme in Computer Science
MSc Programme in Bioinformatics
Knowledge in
- Convex hulls and algorithms to find them.
- Polygon triangulations and algorithms to find them.
- Selected range search methods.
- Selected point location methods.
- Voronoi diagrams and Delaunay triangulations and algorithms to find them.
- Selected algorithms for robot motion and visibility problems.
- Geometric paradigms (e.g. plane sweep, fractional cascading, prune-and-search).
Skills to
- Describe, implement and use selected basic algorithms for solving geometric problems (e.g. convex hulls, localization, searching, visibility graphs).
- Apply geometric paradigms (e.g. plane sweep, fractional cascading, prune and search) and data structures (e.g. Voronoi diagrams, Delaunay triangulations, visibility graphs) to solve geometric problems.
- Present a scientific paper where computational geometry plays a crucial role.
- Read computational geometry papers in scientific journals.
Competences to
- Evaluate which methods are best suited for solving problems involving geometrical properties.
Lectures, group work and presentations.
See Absalon when the course is set up.
Bachelor's level course in algorithms and data structures or
similar.
Academic qualifications equivalent to a BSc degree is
recommended.
As
an exchange, guest and credit student - click here!
Continuing Education - click here!
PhD’s can register for MSc-course by following the same procedure as credit-students, see link above.
- ECTS
- 7,5 ECTS
- Type of assessment
-
Oral examination, 25 minutes
- Type of assessment details
- The oral examination is without preparation.
- Examination prerequisites
-
Seminar presentation and solution of 50% of the problems (spread over 6 assignments).
- Aid
- All aids allowed
- Marking scale
- 7-point grading scale
- Censorship form
- No external censorship
Several internal examiners
- Re-exam
-
Same as ordinary exam.
To qualify for the re-exam 50% out of 6 assignments must be handed in and approved no later than two weeks prior to re-exam date.
Criteria for exam assessment
See Learning Outcome.
Single subject courses (day)
- Category
- Hours
- Lectures
- 20
- Preparation
- 115
- Theory exercises
- 60
- Seminar
- 10
- Exam
- 1
- English
- 206
Kursusinformation
- Language
- English
- Course number
- NDAK10009U
- ECTS
- 7,5 ECTS
- Programme level
- Full Degree Master
- Duration
-
1 block
- Placement
- Block 3
- Schedulegroup
-
B
- Capacity
- No limitation – unless you register in the late-registration period (BSc and MSc) or as a credit or single subject student.
- Studyboard
- Study Board of Mathematics and Computer Science
Contracting department
- Department of Computer Science
Contracting faculty
- Faculty of Science
Course Coordinator
- Mikkel Vind Abrahamsen (4-706c646543676c316e7831676e)
Teacher
Mikkel Abrahamsen, Pawel Winter
Er du BA- eller KA-studerende?
Kursusinformation for indskrevne studerende