Person in charge:  () 
Others:  () 
Credits  Dept.  Type  Requirements 

7.5 (6.0 ECTS)  MAT 

AL
 Prerequisite for DIE , DCSYS CAL  Prerequisite for DIE , DCSYS 
Person in charge:  () 
Others:  () 
We will 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.
We will give 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.
Estimated time (hours):
T  P  L  Alt  Ext. L  Stu  A. time 
Theory  Problems  Laboratory  Other activities  External Laboratory  Study  Additional time 

T  P  L  Alt  Ext. L  Stu  A. time  Total  

2,0  0  0  0  0  1,0  0  3,0  
The problems studied in Computational Geometry. Applications. Terminology. Basic Tools.


T  P  L  Alt  Ext. L  Stu  A. time  Total  

2,0  1,0  3,0  0  3,0  1,0  0  10,0  
Oriented area. Left/right. Intersection of two lines. Intersection of two segments. Oriented turn.


T  P  L  Alt  Ext. L  Stu  A. time  Total  

4,0  2,0  0  0  0  3,0  0  9,0  
Algorithms for the construction od the convex hull of 2D point sets. Convex hull in 3D.


T  P  L  Alt  Ext. L  Stu  A. time  Total  

4,0  2,0  0  0  0  4,0  0  10,0  
Geometric duality. The parabola duality. Intersection of halfplanes and convex hulls. Linear algorithm for LP problems.


T  P  L  Alt  Ext. L  Stu  A. time  Total  

4,0  2,0  0  0  0  3,0  0  9,0  
Triangulation of monotone polygons, decomposition of a polygon into monotone polygons.


T  P  L  Alt  Ext. L  Stu  A. time  Total  

7,0  2,0  2,0  0  3,0  6,0  0  20,0  
Voronoi Diagram


T  P  L  Alt  Ext. L  Stu  A. time  Total  

5,0  2,0  5,0  0  10,0  4,0  0  26,0  
Delaunay triangulation


T  P  L  Alt  Ext. L  Stu  A. time  Total  

4,0  1,0  0  0  0  3,0  0  8,0  
Arrengements of lines. Arrengements of segments.


T  P  L  Alt  Ext. L  Stu  A. time  Total  

2,0  0  0  0  0  1,0  0  3,0  
Point location in planar decompositions.


T  P  L  Alt  Ext. L  Stu  A. time  Total  

6,0  0  0  0  10,0  12,0  0  28,0  
Extensions of the course contents.

Total per kind  T  P  L  Alt  Ext. L  Stu  A. time  Total 
42,0  14,0  14,0  0  30,0  40,0  0  140,0  
Avaluation additional hours  7,0  
Total work hours for student  147,0 
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 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, or explain the troubles that they have encountered while trying to solve them. The problems will be mainly algorithmic (not theoretical).
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 problems, preferably applied and real, to be chosen by each student.
COURSE OPTION:
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)
Common lab exercises (L1)
Free lab exercise (L2)
The final course grade will be calculated as follows:
Final grade = 0.25*P + 0.25*T + 0.35*L1 + 0.15*L2
**************************************************************************
FINAL OPTION:
If they ask for it, students who wish can take a final exam, consisting in solving problems in which the knowledge and skills acquired in class will be applied. In this case, the final course grade will be computed combining the grade of the free lab exercise (L2) and the grade of the final exam (E), in the following way:
Final grade = 0.7*E + 0.3*L2
 Programming with C++
 Basic knowledge of data structures
 Basic knowledge of algorithmic techniques