Geometria Computacional (GEOC)

Presentar els algorismes geomètrics més freqüents que es troben darrera de moltes aplicacions informàtiques en àmbits tals com la informàtica gràfica, la visualització, la reconstrucció de formes, la visió per ordinador, els sistemes d'informació geogràfica, la robòtica, etc.

Donar les eines adequades per al tractament de dades geomètriques massives (algorismes i estructures de dades) i explotar les propietats geomètriques dels problemes plantejats, per trobar-ne solucions òptimes.

Coneixements

1. Conèixer els diversos tipus de problemes que estudia la Geometria Computacional, així com les seves aplicacions.
   
2. Conèixer les capacitats de la combinació de les eines geomètriques amb les estructures de dades i els paradigmes algorísmics més adequats.
3. Veure en acció diversos paradigmes algorísmics i diverses estructures de dades útils en problemes geomètrics.
4. Aplicar resultats geomètrics a problemes reals.
   

Habilitats

1. Saber resoldre problemes bàsics que es plantegen a la geometria computacional.
   
2. Saber implementar les solucions plantejades a classe o les que es troben a la bibliografia bàsica de l'assignatura.
3. Saber reconèixer els problemes geomètrics subjacents a les aplicacions, i proposar eines algorísmiques adequades per resoldre'ls.

Competències

1. Capacitat per crear i utilitzar models geomètrics reals, 2D i 3D.
2. Capacitat per analitzar problemes: distingir les característiques geomètriques del problema, descriure correctament les dades (input) i definir amb precisió la informació geomètrica que es vol obtenir (output).
3. Capacitat d'enfrontar-se a problemes nous recorrent conscientment a estratègies que han estat útils en problemes resolts anteriorment.

A les classes de teoria s'exposaran els continguts de l'assignatura, orientats a la resolució d'exemples i aplicacions.

Les classes de problemes consistiran en la resolució de problemes per part dels estudiants. Aquests problemes s'hauran enunciat i assignat amb prou antel·lació per tal que els estudiants encarregats de la seva resolució els hagin pogut pensar i puguin plantejar a la classe o bé les seves propostes de solució o bé els entrebancs amb què s'hagin trobat en intentar resoldre'ls. Els problemes seran de caire algorísmic (no teòric).

L'objectiu de les classes de laboratori és implementar les solucions discutides a les classes de teoria i problemes, ja que la solució efectiva de problemes és objectiu de l'assignatura. Els problemes a resoldre a classe de laboratori començaran sent de complexitat elemental, per acabar amb la resolució d'un problema, preferiblement aplicat i real, a triar per cada estudiant.

OPCIÓ CURS:

Es tindrà en compte el treball dut a terme per cada estudiant all llarg del curs. Les quatre notes a considerar seran:

Problemes presentats a classe (P)
Exposició final del tema triat (T)
Exercicis comuns de laboratori (L1)
Exercici lliure de laboratori (L2)

La nota final de l'assignatura es calcularà d'acord amb les ponderacions següents:

Nota Final = 0.25*P + 0.25*T + 0.35*L1 + 0.15*L2

**************************************************************************

OPCIÓ FINAL:

A petició de la persona interessada, els estudiants que ho desitgin podran presentar-se a un examen final que consistirà en la resolució de problemes on s'utilitzin els coneixements i les habilitats adquirits a les classes de teoria i de problemes. En aquest cas, la nota final es calcularà a partir de la nota de l'exercici lliure de laboratori (L2) i la de l'examen (E), de la manera següent:

Nota Final = 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
   Article breu i clar que explica què és la Geometria Computacional i per a què serveix.



2. http://www-ma2.upc.es/~geoc
   Pàgina de l'assignatura.

- Programació amb C++
- Coneixements bàsics d'estructures de dades
- Coneixements bàsics de tècniques algorísmiques