Geometría Computacional

Usted está aquí

Inicio » Estudios » Grados » Grado en Ingeniería Informática » Plan de estudios » Asignaturas » Geometría Computacional
Créditos
6
Tipos
Optativa
Requisitos
Esta asignatura no tiene requisitos, pero tiene capacidades previas
Departamento
MAT
Web
https://dccg.upc.edu/courses-geoc/
Mail
En este curso se presentan 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.

Se aprenden 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

Profesorado

Responsable

  • Rodrigo Ignacio Silveira ( )

Horas semanales

Teoría
2
Problemas
1.1
Laboratorio
0.9
Aprendizaje dirigido
0
Aprendizaje autónomo
6

Competencias

Competencias Transversales

Lengua extranjera

  • G3 [Avaluable] - Conocer el idioma inglés con un nivel adecuado de forma oral y por escrito, y con consonancia con las necesidades que tendrán los graduados y graduadas en ingeniería informática. Capacidad de trabajar en un grupo multidisciplinar y en un entorno multilingüe, y de comunicar, tanto por escrito como de forma oral, conocimientos, procedimientos, resultados e ideas relacionadas con la profesión de ingeniero técnico en informática.
    • G3.2 - Estudiar con materiales escritos en inglés. Redactar un informe o trabajo de tipo técnico en inglés. Participar en una reunión técnica llevada a cabo en inglés.

Objetivos

  1. Conocer los diversos tipos de problemas que estudia la Geometría Computacional, así como sus aplicaciones.
    Competencias relacionadas:
  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.
    Competencias relacionadas:
  3. Ver en acción diversos paradigmas algorítmicos y diversas estructuras de datos útiles en problemas geométricos.
    Competencias relacionadas:
  4. Aplicar resultados geométricos a problemas reales.
    Competencias relacionadas:
  5. Saber resolver problemas básicos que aparecen en geometría computacional.
    Competencias relacionadas:
  6. Saber implementar las soluciones planteadas en clase o las que se encuentran en la bibliografía básica de la asignatura.
    Competencias relacionadas:
  7. Saber reconocer los problemas geométricos subyacentes en las aplicaciones, y proponer herramientas algorítmicas adecuadas para resolverlos.
    Competencias relacionadas:
  8. Practicar y mejorar la capacidad de trabajar en un entorno prefesional en lengua inglesa
    Competencias relacionadas: G3.2, G3.3, G3.1,

Contenidos

  1. Introducción a la Geometría Computacional
    Los problemas estudiados por la Geometría Computacional. Aplicaciones. Terminología. Herramientas básicas.
  2. Una herramienta básica
    Área orientada. Izquierda/derecha. Intersección de dos rectas. Intersección de dos segmentos. Giro orientado.
  3. Algoritmos de barrido
    Algoritmo de Bentley-Ottmann
  4. Problemas geométricos básicos sobre polígonos
    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.
  5. Envolvente convexa
    Algoritmos de construcción de la envolvente convexa de una nube de puntos 2D.
  6. Dualidad. Intersección de semiplanos
    Dualidad geométrica. La dualidad asociada a la parábola unidad. Intersección de semiplanos y envolvente convexa.
  7. Triangulación de polígonos
    Triangulación de polígonos monótonos, descomposición de un polígono en polígonos monótonos.
  8. Proximidad
    Diagramas de Voronoi y sus aplicaciones
  9. Triangulaciones de nubes de puntos
    Triangulación de Delaunay
  10. Arreglos de rectas y planos
    Descripción, propiedades y construcción. Niveles. Relación con los diagramas de Voronoi.
  11. Localización en descomposiciones del plano
    Diversidad de estrategias. Complejudad del preprocesado vs eficiencia de las consultas.
  12. Reconstrucción de formas
    Alpha-shapes, crust, anti-crust y beta-skeletons.
  13. Presentación de temas por parte de los estudiantes
    Extensiones del temario de la asignatura.

Actividades

Actividad Acto evaluativo



Resolución de problemas

Sólo algunas sesiones correrán a cargo de la profesora. El resto consistirá en la presentación y discusión de la resolución de problemas por parte de los estudiantes.
Objetivos: 5 7 8
Contenidos:
Teoría
0h
Problemas
16.5h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
25h

Laboratorio

Implementación de algoritmos geométricos
Objetivos: 4 6 8
Contenidos:
Teoría
0h
Problemas
0h
Laboratorio
13.5h
Aprendizaje dirigido
0h
Aprendizaje autónomo
45h


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 del profesorado y 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 sus propuestas de solución. Los problemas tendrán carácter algorítmico.

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.

Método de evaluación

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 de laboratorio (L)
Examen (E)

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

Final grade = 0.2*P + 0.2*T + 0.35*L + 0.25*E

Bibliografía

Básica:

Complementaria:

Web links

Capacidades previas

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

Esta asignatura se recomienda para estudiantes con conocimientos e interés en computación. Se recomienda a los estudiantes de otras especialidades o sin especialidad que lo tengan en cuenta al matricularse.

Los estudiantes deben hacer sus presentaciones en inglés. No se recomienda la asignatura a estudiantes con niveles de inglés muy rudimentarios.