Computational Geometry (CG)

Course content

The purpose of this course is to introduce the students to the methods for solving problems where geometrical properties are of particular importance. We will look at some basic problems; at algorithmic paradigms especially suited to solve such problems, and at geometric data structures. We will also look at the applications of computational geometry in relation to the problems of for example molecular biology. No a priori knowledge of molecular biology is required. During the course, the students will be asked to make a project proposal (7.5 or 15 ECTS) which they will have the opportunity to work on in the following block.

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.

 

Education

MSc Programme in Computer Science

MSc Programme in Bioinformatics

Learning outcome

Knowledge in

  • Convex hulls and algorithms for their determination.
  • Polygon triangulations and algorithms for their determination.
  • Selected range search methods.
  • Selected point location methods.
  • Voronoi diagrams and Delaunay triangulations and algorithms for their determination.
  • 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.

Written
Oral
Individual
Feedback by final exam (In addition to the grade)
Peer feedback (Students give each other feedback)
ECTS
7,5 ECTS
Type of assessment
Oral examination, 20 minutes
Type of assessment details
The oral examination is without preparation.
Exam registration requirements

Seminar presentation and solution of what is corresponding to 50% out of 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-7c7870714f73783d7a843d737a)
Teacher

Mikkel Abrahamsen, Pawel Winter

Saved on the 25-06-2024

Er du BA- eller KA-studerende?

Er du bachelor- eller kandidat-studerende, så find dette kursus i kursusbasen for studerende:

Kursusinformation for indskrevne studerende