NDAK10009U Computational Geometry
Volume
2014/2015  Language  English   Credit  7,5 ECTS   Level  Full Degree Master   Duration  1 block   Placement  Block 3  Schedule  C (Mon 1317 + Wednes 817)   Course capacity  No limit.  Continuing and further
education   Study board  Study Board of Mathematics and Computer
Science   Contracting department   Department of Computer Science
  Course responsible   Pawel Winter (574657b697044686d326f7932686f)
  Saved on the
04122014 
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 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 VLSIdesign, pattern recognition,
image processing, operations research and statistics and molecular
biology.  Learning Outcome  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,
pruneandsearch).
 Literature  See Absalon when the course is set up.  Teaching and learning methods  5 weeks lectures, 2 weeks group work, 2 weeks
paper presentations 
Academic qualifications  Bachelor's level course in algorithms and
data structures. 
Sign up  Self Service at KUnet

Exam  Credit  7,5 ECTS   Type of assessment  Oral examination, 20 minutes Oral 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  7point 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.


Workload  Category  Hours  Lectures  20  Colloquia  10  Preparation  115  Theory exercises  60  Exam  1  Total  206 

Saved on the
04122014

