Computional Geometry 7.5 Credits

Algoritmer för geometriska problem
Second cycle, D7013E
Course syllabus valid: Autumn 2012 Sp 1 - Present
The version indicates the term and period for which this course syllabus is valid. The most recent version of the course syllabus is shown first.

Syllabus established
by the Department of Computer Science and Electrical Engineering 17 Dec 2007

Last revised
by Jonny Johansson, HUL SRT 12 Mar 2012

Education level
Second cycle
Grade scale
G U 3 4 5
Computer Science
Subject group (SCB)
Computer Technology

Entry requirements

To take this course you have to know how to program computers and analyze algorithms and data structures. The two courses D0010E and D0012E give a minimum suitable background.

More information about English language requirements


Selection C

Course Aim

After the course, the student

  1. shows great knowledge about the scientific foundation of the field of Computational Geometry in terms of the construction, presentation, and analysis of algorithms and data structures for geometric problems and an considerable degree of specialized knowledge in certain parts of the theory of algorithms;
  2. demonstrates an extensive ability to identify, formulate and deal with complex algorithmic issues autonomously and critically and with a holistic approach;
  3. demonstrates an ability to create, analyse and critically evaluate various algorithmic solutions, and an ability to plan and use appropriate methods to implement advanced algorithmic solutions within predetermined parameters and based on proven experience;
  4. demonstrates an ability to present his or her own conclusions regarding solutions to algorithmic problems with a geometric flavour, and the knowledge and arguments on which they are based, in speech and writing to different audiences;
  5. show insight into current research and development.


Examples of practical applications where algorithms and data structures from the field of Computational Geometry are applicable, like Robotics, Computer Graphics, VLSI-design, Virtual Reality, Geographical Information Systems (GIS), and Computer-Aided Design/Manufacturing (CAD/CAM).

The course covers the following theory: Polygons, triangulations, visibility, art gallery problems, convex hulls, Voronoi and Delaunay diagrams, proximity problems, point location search, arrangements of lines, hyper-planes; geometric duality, visibility graphs, shortest paths, motion planning, and intersection problems.


Lectures, mandatory programming assignments, projects and/or seminars. At some lectures it is the students that present their solutions to homework given after the regular lectures. Presenting and discussing solved solutions in the class gives a bonus that counts towards passing the final written exam. Solving homework is optional, but highly recommended, and also those that have not solved problems are welcome to join the discussions. The programming assignments aim at becoming familiar with the programming environment and get to know some primary scientific sources (journals and conferences). The project is about implementing a geometric algorithm/data structure and presenting it for the class.


A final written exam with differentiated grades (goals 1 and 2), a project that must be completed in time (3 and 5) and presented (4).

The course will not be given every year.

Transition terms

The course D7013E is equal to the old course SMD156.

Håkan Jonsson

Transition terms
The course D7013E is equal to SMD156

Literature. Valid from Autumn 2012 Sp 1 (May change until 10 weeks before course start)
Scientific papers.
de Berg, van Kreveld, Overmars och Schwartzkopf, Computational Geometry: Algorithms and Applications, 3rd edition.

Course offered by
Department of Computer Science, Electrical and Space Engineering

0002Project4.0U G#
0004Written exam3.5G U 3 4 5

Study guidance