NDAK10009U Computational Geometry
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 to the problems of
molecular biology in particular. 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 ETCS) 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 and statistics and molecular
biology.
Competences
- Evaluate which methods are best suited for solving problems involving geometrical properties.
Skills
- 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.
Knowledge
- 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).
See Absalon when the course is set up.
- Category
- Hours
- Colloquia
- 10
- Exam
- 1
- Lectures
- 20
- Preparation
- 115
- Theory exercises
- 60
- Total
- 206
As
an exchange, guest and credit student - click here!
Continuing Education - click here!
- Credit
- 7,5 ECTS
- Type of assessment
- Oral examination, 20 minutesOral examination without preparation.
- Exam registration requirements
- Seminar presentation and solution of what is corresponding to 3 out of 6 assignments.
- Aid
- All aids allowed
- Marking scale
- 7-point grading scale
- Censorship form
- No external censorship
One internal examiner.
Criteria for exam assesment
In order to achieve the highest grade 12, a student must be able to
- define the problems introduced during the course
- explain the algorithms and data structures for solving these problems,
- explain the geometric paradigms introduced during the course
- discuss the content of the paper covered by the student's group in the seminar presentation.
Course information
- Language
- English
- Course code
- NDAK10009U
- Credit
- 7,5 ECTS
- Level
- Full Degree Master
- Duration
- 1 block
- Placement
- Block 3
- Schedule
- C (Mon 13-17 + Wednes 8-17)
- Course capacity
- No limit.
- Continuing and further education
- Study board
- Study Board of Mathematics and Computer Science
Contracting department
- Department of Computer Science
Course responsibles
- Pawel Winter (5-77687e6c73476b7035727c356b72)