In this course we present the most frequent geometric algorithms behind many computer science applications in fields such as computer graphics, visualization, shape reconstruction, computer vision, geographical information systems, robotics, etc.
You will learn the appropriated tools for dealing with massive geometric data (algorithms and data structures) and will exploit the geometric properties of the problems posed, to find optimal solutions.
Person in charge
Vera Sacristan Adinolfi (
Rodrigo Ignacio Silveira (
G3 - To know the English language in a correct oral and written level, and accordingly to the needs of the graduates in Informatics Engineering. Capacity to work in a multidisciplinary group and in a multi-language environment and to communicate, orally and in a written way, knowledge, procedures, results and ideas related to the technical informatics engineer profession.
- To study using resources written in English. To write a report or a technical document in English. To participate in a technical meeting in English.
Learn the several kinds of problems in Computational Geometry, as well as their applications.
Learn the capacity of combining geometric tools with the appropriated data structures and algorithmic paradigms.
See in action several algorithmic paradigms and data structures useful in geometric problems.
Apply geometric results to real problems.
Ability to solve basic problems that appear in computational geometry.
Ability to implement the solutions proposed in the class, as well as those that can be found in the basic references of the course.
Ability to recognize the geometric problems behind the applications, and to propose adequate algorithmic tools to solve them.
Practice and improve the capability of working in a English speaking professional surrounding
Introduction to Computational Geometry
The problems studied in Computational Geometry. Applications. Terminology. Basic Tools.
A basic tool
Oriented area. Left/right. Intersection of two lines. Intersection of two segments. Oriented turn.
Sweep line algorithms
Basic geometric problems on polygons
Line/polygon intersection, point location in a polygon, supporting lines to a polygon from a point, etc.
Algorithms for the construction od the convex hull of 2D point sets.
Duality. Intersection of halfplanes.
Geometric duality. The parabola duality. Intersection of halfplanes and convex hulls.
Triangulation of monotone polygons, decomposition of a polygon into monotone polygons.
Voronoi diagrams and their applications
Triangulations of point sets
Line and plane arrangements
Description, properties, and construction. Levels. Relationship with Voronoi diagrams.
Point location in planar subdivisions
Variety of strategies. Preprocessing complexity vs query efficiency.
Alpha-shapes, crust, anti-crust and beta-skeletons.
Students presentations of further subjects
Extensions of the course contents.
Students will be in charge of the final sessions. Objectives:1238 Contents:
Theory classes will set out the contents of the course, oriented to the resolution of examples and applications.
Exercise classes will be centered in the resolution of problems by the instructors as well as by the students. Students will be assigned problems and will have enough time to think about them in advance, so that they will be able to propose their solutions during the class. The problems will be mainly algorithmic.
The purpose of the lab classes is to implement the solutions discussed in the theory and exercices classes, the effective solution of problems being one of the goals of the course. The problems to be solved in the lab classes will start being of elementary complexity, and will end with the resolution of a problem, preferably applied and real.
The evaluation will be based on the work done by the student along the course. The four components to be considered will be:
Problems presented in class (P)
Final presentation of the chosen subject (T)
Lab exercises (L)
The final course grade will be calculated as follows:
- Basic knowledge of data structures
- Basic knowledge of algorithmic techniques
This course is recommended for students with knowledge and interest in computation. Students with other specializations of without any specialization are kindly asked to take this into account before enrolling.
Students need to do their presentations in English. This course is not recommend for students with very rudimentary English skills.
Where we are
B6 Building Campus Nord
C/Jordi Girona Salgado,1-3
08034 BARCELONA Spain
Tel: (+34) 93 401 70 00