Computational Geometry (GEOC)

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.

Knowledges

1. Learn the several kinds of problems in Computational Geometry, as well as their applications.
2. Learn the capacity of combining geometric tools with the appropriated data structures and algorithmic paradigms.
3. See in action several algorithmic paradigms and data structures useful in geometric problems.
4. Apply geometric results to real problems.

Abilities

1. Ability to solve basic problems that appear in computational geometry.
2. Ability to implement the solutions proposed in the class, as well as those that can be found in the basic references of the course.
3. Ability to recognize the geometric problems behind the applications, and to propose adequate algorithmic tools to solve them.

Competences

1. Ability to create and use real 2D and 3D geometric models.
2. Ability to analize problems: distinguish the geometric characteristics of the problem, properly describe the data (input) and precisely define the geometric information that we want to obtain (output).
3. Ability to tackle new problems by consciously using strategies that have proved useful in solving previous problems.

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

• Joseph O'Rourke. Computational geometry in C, Cambridge University Press, (2nd edition) 1998.
• Mark de Berg ... [et al.] Computational geometry: algorithms and applications, Springer, (3rd edition) 2008.
• Franco P. Preparata, Michael Ian Shamos Computational geometry: an introduction, Springer, (1st edition, corrected 5th printing) 1985.

• Sack J.-R., Urrutia J. (editors) Handbook of computational geometry, Elsevier, 2000.
• Jacob E. Goodman, Joseph O'Rourke, [editors] Handbook of discrete and computational geometry, Chapman & Hall/CRC, 2004.
• Jean-Daniel Boissonat, Mariette Yvinec Algorithmic Geometry, Cambridge University Press, 1998.
• Satyan L. Devadoss, Joseph O'Rourke Discrete and Computational Geometry, Princeton University Press, 2011.

1. http://softsurfer.com/overview.htm
   



2. http://www-ma2.upc.es/~geoc
   

- Programming with C++
- Basic knowledge of data structures
- Basic knowledge of algorithmic techniques