Geometría Computacional

Créditos
6
Tipos
  • GRAU: Optativa
  • GCED: Optativa
Requisitos
Esta asignatura no tiene requisitos , pero tiene capacidades previas
Departamento
MAT
Web
https://dccg.upc.edu/courses-geoc/
Mail
rodrigo.silveira@upc.edu
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

Otros

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.1, G3.2, G3.3,

    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ásico

    Complementario

    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.