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 (
)
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
-
Conocer los diversos tipos de problemas que estudia la Geometría Computacional, así como sus aplicaciones.
Competencias relacionadas:
-
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:
-
Ver en acción diversos paradigmas algorítmicos y diversas estructuras de datos útiles en problemas geométricos.
Competencias relacionadas:
-
Aplicar resultados geométricos a problemas reales.
Competencias relacionadas:
-
Saber resolver problemas básicos que aparecen en geometría computacional.
Competencias relacionadas:
-
Saber implementar las soluciones planteadas en clase o las que se encuentran en la bibliografía básica de la asignatura.
Competencias relacionadas:
-
Saber reconocer los problemas geométricos subyacentes en las aplicaciones, y proponer herramientas algorítmicas adecuadas para resolverlos.
Competencias relacionadas:
-
Practicar y mejorar la capacidad de trabajar en un entorno prefesional en lengua inglesa
Competencias relacionadas:
G3.1,
G3.2,
G3.3,
Contenidos
-
Introducción a la Geometría Computacional
Los problemas estudiados por la Geometría Computacional. Aplicaciones. Terminología. Herramientas básicas.
-
Una herramienta básica
Área orientada. Izquierda/derecha. Intersección de dos rectas. Intersección de dos segmentos. Giro orientado.
-
Algoritmos de barrido
Algoritmo de Bentley-Ottmann
-
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.
-
Envolvente convexa
Algoritmos de construcción de la envolvente convexa de una nube de puntos 2D.
-
Dualidad. Intersección de semiplanos
Dualidad geométrica. La dualidad asociada a la parábola unidad. Intersección de semiplanos y envolvente convexa.
-
Triangulación de polígonos
Triangulación de polígonos monótonos, descomposición de un polígono en polígonos monótonos.
-
Proximidad
Diagramas de Voronoi y sus aplicaciones
-
Triangulaciones de nubes de puntos
Triangulación de Delaunay
-
Arreglos de rectas y planos
Descripción, propiedades y construcción. Niveles. Relación con los diagramas de Voronoi.
-
Localización en descomposiciones del plano
Diversidad de estrategias. Complejudad del preprocesado vs eficiencia de las consultas.
-
Reconstrucción de formas
Alpha-shapes, crust, anti-crust y beta-skeletons.
-
Presentación de temas por parte de los estudiantes
Extensiones del temario de la asignatura.
Actividades
Actividad
Acto evaluativo
Presentaciones de teoría
Las sesiones finales serán a cargo de los estudiantes.
Objetivos:
1
2
3
8
Contenidos:
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:
Laboratorio
Implementación de algoritmos geométricos
Objetivos:
4
6
8
Contenidos:
Examen
Consiste en la resolución de algun(os) problema(s) y de alguna(s) cuestión(es) de teoría.
Objetivos:
1
2
3
4
5
7
Contenidos:
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:
-
Computational geometry: algorithms and applications -
Berg, Mark de; [et al.],
Springer-Verlag, 2008. ISBN: 9783540779735
https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003394369706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
-
Computational geometry in C -
O'Rourke, J,
Cambridge University Press, 1998. ISBN: 0521640105
https://discovery.upc.edu/discovery/fulldisplay?docid=alma991001826749706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
-
Computational geometry: an introduction -
Preparata, F.P.; Shamos, M.I,
Springer-Verlag, 1985. ISBN: 3540961313
https://discovery.upc.edu/discovery/fulldisplay?docid=alma991000025139706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
Complementaria:
-
Algorithmic geometry -
Boissonnat, J.-D.; Yvinec, M, Cambridge University Press ,
1997.
ISBN: 0521565294
https://discovery.upc.edu/discovery/fulldisplay?docid=alma991001667769706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
-
Discrete and computational geometry -
Devadoss, S.L.; O'Rourke, J., Princenton University Press ,
2011.
ISBN: 9780691145532
https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003871229706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
-
Handbook of computational geometry -
Sack, J.-R.; Urrutia, J, Elsevier ,
2000.
ISBN: 0444825371
https://discovery.upc.edu/discovery/fulldisplay?docid=alma991002018899706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
-
Handbook of discrete and computational geometry -
Goodman, J.E.; O'Rourke, J, Chapman & Hall/CRC ,
2004.
ISBN: 1584883014
https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003283509706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
-
Voronoi diagrams and Delaunay triangulations -
Aurenhammer, F.; Klein, R.; Lee, D.-T, World Scientific ,
2013.
ISBN: 9789814447638
https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003996099706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
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.