1. Introducció. Exemples d'aplicació: Google Maps, sistemes de navegació GPS, recerques locals (restaurants de Girona).
2. Subdivisions planars i la seva representació: DCEL, etc. Localització de punts en subdivisions planars.
3. Interseccions d'un conjunt de segments. Intersecció de polígons. Superposició de subdivisions planars. Simplificació de línies poligonals.
4. Triangulació d'un polígon. Triangulació d'un conjunt de punts. Triangulació de Delaunay.
5. Diagrama de Voronoi. Problemes de proximitat.
6. Estructures de dades espacials: quadtree, kd-tree, R-tree, etc. Cerca en rangs ortogonals.
7. Càlcul dels k-veïns més propers i k-veïns reversos més propers.
8. Representació de xarxes espacials (carreteres, carrers, etc).Models de terrenys: xarxes irregulars trianguladas (TINs).
9. Càlculs en xarxes espacials i TINs: camí més curt, diagrama de Voronoi, etc.
10. Patrons de moviment en bases de dades de trajectòries.
Avaluació del treball fet a les sessions pràctiques (25%) i del projecte final de la assignatura (75%). En ambdós casos no hi haurà recuperació.
Criteris específics de la nota «No Presentat»:
Es considerarà no presentat a qui no hagi entregat el treball fet a les sessions pràctiques o no hagi entregat el projecte final de l'assignatura.