Saltar al contingut Menu
Mapa
  • Inicio
  • Información
  • Contacto
  • Mapa

Geometría Computacional (GEOC)

Créditos Dept.
7.5 (6.0 ECTS) MAT

Profesores

Responsable:  (-)
Otros:(-)

Objectivos Generales

Presentar los algoritmos geométricos más frecuentes que que se hallan tras muchas aplicaciones informáticas en ámbitos tales como la informática gráfica, la visualitzación, la reconstrucción de formas, la visión por ordenador, los sistemas de información geográfica, la robótica, etc.

Dar les herramientas adecuadas pera el tratamiento de datos geométricos masivos (algoritmos y estructuras de datos) y explotar las propiedades geométricas de los problemas planteados, para hallar soluciones óptimas.

Objectivos Específicos

Conocimientos

  1. Conocer los diversos tipos de problemas que estudia la Geometría Computacional, así como sus aplicaciones.
  2. Conocer las capacidades de la combinación de las herramientas geométricas con las estructuras de datos y los paradigmas geométricos más adecuados.
  3. Ver en acción diversos paradigmas algorítmicos y diversas estructuras de datos útiles en problemas geométricos.
  4. Apricar resultados geométricos a problemas reales.

Habilidades

  1. Saber resolver problemas básicos que aparecen en geometría computacional.
  2. Saber implementar las soluciones planteadas en clase o las que se encuentran en la bibliografía básica de la asignatura.
  3. Saber reconocer los problemas geométricos subyacentes en las aplicaciones, y proponer herramientas algorítmicas adecuadas para resolverlos.

Competencias

  1. Capacidad para crear y utilizar modelos geométricos reales, 2D y 3D.
  2. Capacidad para analizar problemas: distinguir las características geométricas del problema, describir correctamente los datos (input) y definir con precisión la información geométrica que se quiere obtener (output).
  3. Capacidad para enfrentarse a problemas nuevos recurriendo conscientemente a estrategias que han sido útiles en problemas resueltos anteriormente.

Contenidos

Horas estimadas de:

T P L Alt L Ext. Est O. Ext.
Teoria Problemas Laboratorio Otras actividades Laboratorio externo Estudio Otras horas fuera del horario fijado

1. Introducción a la Geometría Computacional
T      P      L      Alt    L Ext. Est    O. Ext. Total 
2,0 0 0 0 0 1,0 0 3,0
Los problemas estudiados por la Geometría Computacional. Aplicaciones. Terminología. Herramientas básicas.

2. Una herramienta básica
T      P      L      Alt    L Ext. Est    O. Ext. Total 
2,0 1,0 3,0 0 3,0 1,0 0 10,0
Área orientada. Izquierda/derecha. Intersección de dos rectas. Intersección de dos segmentos. Giro orientado.

3. Problemas geométricos básicos sobre polígonos
T      P      L      Alt    L Ext. Est    O. Ext. Total 
2,0 2,0 4,0 0 4,0 2,0 0 14,0
Intersección recta/polígono, localización de un punto en un polígono, rectas de soporte a un polígono desde un punto, etc.

4. Envolvente convexa
T      P      L      Alt    L Ext. Est    O. Ext. Total 
4,0 2,0 0 0 0 3,0 0 9,0
Algoritmos de construcción de la envolvente convexa de una nube de puntos 2D. Envolvente 3D.

5. Dualidad. Intersección de semiplanos. Programación lineal
T      P      L      Alt    L Ext. Est    O. Ext. Total 
4,0 2,0 0 0 0 4,0 0 10,0
Dualidad geométrica. La dualidad asociada a la parábola unidad. Intersección de semiplanos y envolvente convexa. Algoritmo lineal para los problemas de programación lineal.

6. Triangulación de polígonos
T      P      L      Alt    L Ext. Est    O. Ext. Total 
4,0 2,0 0 0 0 3,0 0 9,0
Triangulación de polígonos monótonos, descomposición de un polígono en polígonos monótonos.

7. Proximidad
T      P      L      Alt    L Ext. Est    O. Ext. Total 
7,0 2,0 2,0 0 3,0 6,0 0 20,0
Diagrama de Voronoi

8. Triangulaciones de nubes de puntos
T      P      L      Alt    L Ext. Est    O. Ext. Total 
5,0 2,0 5,0 0 10,0 4,0 0 26,0
Triangulación de Delaunay

9. Arreglos
T      P      L      Alt    L Ext. Est    O. Ext. Total 
4,0 1,0 0 0 0 3,0 0 8,0
Arreglos de rectas. Arreglos de segmentos.

10. Localización
T      P      L      Alt    L Ext. Est    O. Ext. Total 
2,0 0 0 0 0 1,0 0 3,0
Localización de puntos en descomposiciones del plano.

11. Exposición de problemas estudiados por los estudiantes
T      P      L      Alt    L Ext. Est    O. Ext. Total 
6,0 0 0 0 10,0 12,0 0 28,0
Extensiones del temario de la assignatura.


Total por tipo T      P      L      Alt    L Ext. Est    O. Ext. Total 
42,0 14,0 14,0 0 30,0 40,0 0 140,0
Horas adicionales dedicadas a la evaluación 7,0
Total horas de trabajo para el estudiante 147,0

Metodología docente

En las clases de teoría se expondrán los contenidos de la asignatura, orientados a la resolución de ejemplos y aplicaciones.

Las clases de problemas conisistirán en la resolución de problemas por parte de los estudiantes. Estos problemas habrán sido enunciados y asignados con suficiente antelación para que los estudiantes encargados de su resolución los hayan podido pensar y puedan plantear en clase o bien sus propuestas de solución o bien los obstáculos con los que se hayan encontrado al intentar resolverlos. Los problemas tendrán carácter algorítmico (no teórico).

El objectivo de las clases de laboratorio es implementar las soluciones discutidas en las clases de teoría y problemas, ya que la solución efectiva de problemas es objectivo de la asignatura. Los problemas a resolver en clase de laboratorio empezarán siendo de complejidad elemental, para acabar con la resolución de un problema, preferiblemente aplicado y real, a elegir por cada estudiante.

Método de evaluación

OPCIÓN CURSO:

Se tendrá en cuenta el trabajo llevado a cabo por cada estudiante a lo largo del curso. Las cuatro notas a considerar serán:

Problemas presentados en clase (P)
Exposición final del tema escogido (T)
Ejercicios comunes de laboratorio (L1)
Ejercicio libre de laboratorio (L2)

La nota final de la asignatura se calculará de acuerdo con las ponderaciones siguientes:

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

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

OPCIÓN FINAL:

A petición de la persona interesada, los estudiantes que lo deseen podrán presentarse a un examen final que consistirá en la resolución de problemas en los que se utilicen los conocimientos y las habilidades adquiridos en las clases de teoría y problemas. En este caso, la nota final se calculará a partir de la nota del ejercicio libre de laboratorio (L2) i la del examen (E), de la manera siguiente:

Nota Final = 0.7*E + 0.3*L2

Bibliografía básica

  • 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.

Bibliografía complementaria

  • 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.

Enlaces web

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


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


Capacidades previas

- Programación con C++
- Conocimientos básicos de estructuras de datos
- Conocimientos básicos de técnicas algorítmicas


Compartir

 
logo FIB © Facultad de Informática de Barcelona - Contacto - RSS
Esta web utiliza cookies propias para ofrecerle una mejor experiencia y servicio. Si continúa la navegación, entendemos que acepta nuestra política de cookies. Versión clássica Versión móvil