Servicios
AGENDA UNL | FICH
ESTUDIOS | Carreras de grado | Ingeniería en Informática | Geometría Computacional

    Planificación de Geometría Computacional (2018)

     IMPRIMIR PLANIFICACIÓN

    Información básica

    Carrera
    Ingeniería en Informática
    Departamento
    Informática
    Sitio Web
    http://e-fich.unl.edu.ar/moodle/course/view.php?id=178
    Plan de Estudios
    Plan 2006
    Carácter Período
    Cuatrimestral 0
    Docente Responsable
    Nestor Alberto Calvo

    Equipo docente

    Nombre y Apellido
    Calvo, Nestor Alberto

    Carga horaria

    Carga horaria total 60 hs
    Teoría 30 hs
    Resolución de ejercicios 0 hs
    Proyecto y diseño 10 hs
    Evaluaciones 0 hs
    Formación experimental 10 hs
    Resolución de problemas de ingeniería 10 hs
    Otras actividades 0 hs

    Contenidos mínimos

    Algoritmos geométricos ejemplares: Analisis de costo computacional, robustez y tratamiento de casos patológicoa, aspectos importantes en la implementación. Aplicaciones a la computación gráfica, robótica, sistemas de información geográfica (GIS), diseño y fabricación asistidas por computadora (CAD-CAM), generación de mallas, etc.

    Objetivos

    Se pretende dotar al alumno de las competencias necesarias para analizar y diseñar algoritmos eficientes y robustos para la resolución de problemas que pueden plantearse en términos geométricos. La presentación se hará a través de una serie de algoritmos ejemplares, seleccionados para entender los conceptos generales. Se estudiará la eficiencia y robustez de los algoritmos y los métodos para abordar los casos patológicos. El objetivo primario es que el alumno aprenda a razonar con la lógica particular de éste tipo de algoritmos.

    Conocimientos específicos previos para cursar la asignatura

    Algoritmos y Estructuras de Datos. Programación en C/C++. Cálculo y Geometría Analítica.

    Metodología de enseñanza

    Sigue los lineamientos del libro: Computational Geometry: Algorithms and Applications, M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars, Springer-Verlag, 3 ed. 2008.

    Semanalmente habrá una clase de teoría y practicas que pueden consistir en análisis de literatura técnica y/o el desarrollo de software específico.

    Programa Analítico

    Introducción

    Definición y alcances de la Geometría Computacional.

    Conceptos previos:

    Series numéricas

    Elementos de la Topología: Abierto, Espacio Topológico, Entorno, Frontera, Conexidad, Compacidad, Homeomorfismo, Variedades diferenciales.

    Espacios y transformaciones: Vectorial, Afín, Proyectivo, Métricas. Coordenadas en símplices y funciones de forma.

    Análisis Asintótico y Complejidad algorítmica: Cotas O, o, Ω, ω y θ; Análisis de recursiones y Master Theorem.

    Dualidades: Grafos duales. Incidencia. Dualidad punto/linea: Dualidad Algebraica. Inversión circular – Polaridad. Dualidad Proyectiva y polaridad cónica.111

    Definición y alcances de la Geometría Computacional

    Conceptos previos:

    Series numéricas

    Elementos de la Topología: Abierto, Espacio Topológico, Entorno, Frontera, Conexidad, Compacidad, Homeomorfismo, Variedades diferenciales.

    Espacios y transformaciones: Vectorial, Afín, Proyectivo, Métricas.

    Coordenadas en símplices y funciones de forma.

    Análisis Asintótico y Complejidad algorítmica: Cotas O, o, W, w y Q; Análisis de recursiones y Master Theorem.
    Envoltorio Convexo en el plano

    Clasificación de polígonos: Simple/Autointerceptado. Convexo/Estrella/Visible desde el exterior. Monótono respecto a una línea.

    Definiciones equivalentes de Envoltorio Convexo.

    Algoritmo O(n3) trivial.

    Algoritmos O(n log(n)): Incremental: Graham Scan. Divide and Conquer. Quick Hull

    Algoritmos output-dependent: O(nh): Gift Wrapping y Jarvis March. O(n log(h)): Algoritmo de Chan

    Búsqueda en O(log(n)) de tangentes y Bounding-Box de polígonos convexos.
    Intersecciones de segmentos en el plano

    Algoritmo de barrido plano y estructuras de datos asociadas: Cola de Eventos. Árboles Binarios Auto-Balanceados. Lista Doblemente Enlazada de aristas.

    Operaciones Booleanas entre grafos (mallas) y regiones planas (GIS)
    Triangulación de Polígonos Simples

    Problema del guardián de la galería de arte y triangulaciones. Art Gallery Theorem.

    Partición de un polígono en piezas monótonas: Algoritmo de barrido. Triangulación de polígonos monótonos en tiempo lineal.

    Triangulación de polígonos con fronteras interiores, regiones planas con líneas sueltas y nubes de puntos aislados.
    Programación Lineal

    Desmoldabilidad de poliedros y chapas estampadas.

    Intersección de semiplanos: Algoritmo divide and conquer.

    Programación lineal: Algoritmo incremental. Justificación y backwards analysis para los Algoritmos Aleatorios: Expected Time. Unbounded Linear Programs. Programación lineal en muchas dimensiones

    Problemas parecidos o LP-type problems: Facility planning, Euclidean 1-center o envoltorio esférico. Normales y mínimo casquete envolvente en la esfera unitaria.
    Ubicación de puntos

    Bases de datos y el problema 1D.

    Búsqueda ortogonal.

    Trees y Tries: kD Tree. Octree. BSP tree.

    Búsqueda en triangulaciones por funciones de forma.
    Diagrama de Voronoï y Triangulación Delaunay

    Definiciones y dualidad, propiedades.

    Algoritmo de Fortune: lifting map y coastline.

    Triangulación incremental aleatoria.

    Generación de puntos y mallas.

    Algoritmos en 3D.

    Algoritmos en muchas dimensiones.

    Bibliografía

    Bibliografía básica

    M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars
    Computational Geometry: Algorithms and Applications
    Springer-Verlag

    Apuntes

    Unidad Título Apunte Descripción Descargar

    Cronograma de actividades

    Introducción y Conceptos previos Semana 1 Tipo: T Duración: 4 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:
    Envoltorios Convexos Semana 2 Tipo: T Duración: 3 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:
    Envoltorios Convexos Semana 2 Tipo: PL Duración: 1 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:

    Laboratorio de Informática
    Envoltorios Convexos Semana 3 Tipo: T Duración: 3 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:
    Envoltorios Convexos Semana 3 Tipo: PL Duración: 1 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:

    Laboratorio de Informática
    Intersección de segmentos en el plano Semana 4 Tipo: T Duración: 2 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:
    Intersecciones de segmentos en el plano Semana 4 Tipo: PL Duración: 1 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:

    Laboratorio de Informática
    Intersecciones de segmentos en el plano Semana 4 Tipo: PI Duración: 1 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:

    Laboratorio de Informática
    Triangulación de polígonos simples Semana 5 Tipo: T Duración: 2 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:
    Triangulación de Polígonos Simples Semana 5 Tipo: PL Duración: 1 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:

    Laboratorio de Informática
    Triangulación de Polígonos Simples Semana 5 Tipo: PI Duración: 1 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:

    Laboratorio de Informática
    Triangulación de polígonos simples Semana 6 Tipo: T Duración: 2 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:
    Triangulación de Polígonos Simples Semana 6 Tipo: PL Duración: 1 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:

    Laboratorio de Informática
    Triangulación de Polígonos Simples Semana 6 Tipo: PI Duración: 1 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:

    Laboratorio de Informática
    Programación Lineal Semana 7 Tipo: T Duración: 2 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:
    Programación Lineal Semana 7 Tipo: PL Duración: 1 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:

    Laboratorio de Informática
    Programación Lineal Semana 7 Tipo: PI Duración: 1 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:

    Laboratorio de Informática
    Programación Lineal Semana 8 Tipo: T Duración: 2 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:
    Programación Lineal Semana 8 Tipo: PL Duración: 1 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:

    Laboratorio de Informática
    Programación Lineal Semana 8 Tipo: PI Duración: 1 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:

    Laboratorio de Informática
    Ubicación de puntos (Arboles) Semana 9 Tipo: T Duración: 2 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:
    Ubicación de puntos (Arboles) Semana 9 Tipo: PL Duración: 1 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:

    Laboratorio de Informática
    Ubicación de puntos (Arboles) Semana 9 Tipo: PI Duración: 1 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:

    Laboratorio de Informática
    Ubicación de puntos Semana 10 Tipo: T Duración: 2 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:
    Ubicación de puntos Semana 10 Tipo: PL Duración: 1 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:

    Laboratorio de Informática
    Ubicación de puntos Semana 10 Tipo: P/D Duración: 1 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:

    Laboratorio de Informática
    Diagrama de Voronoï Semana 11 Tipo: T Duración: 2 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:
    Diagrama de Voronoï Semana 11 Tipo: PL Duración: 1 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:

    Laboratorio de Informática
    Diagrama de Voronoï Semana 11 Tipo: P/D Duración: 1 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:

    Laboratorio de Informática
    Dualidad Semana 12 Tipo: T Duración: 2 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:
    Dualidad Semana 12 Tipo: P/D Duración: 2 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:

    Laboratorio de Informática
    Triangulación Delaunay Semana 13 Tipo: T Duración: 2 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:
    Triangulación Delaunay Semana 13 Tipo: P/D Duración: 2 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:

    Laboratorio de Informática
    Apoyo y Evaluación de Prácticas Semana 14 Tipo: PI Duración: 2 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:

    Laboratorio de Informática
    Apoyo y Evaluación de Prácticas Semana 14 Tipo: P/D Duración: 2 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:

    Laboratorio de Informática
    Apoyo y Evaluación de Prácticas Semana 15 Tipo: PI Duración: 2 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:

    Laboratorio de Informática
    Apoyo y Evaluación de Prácticas Semana 15 Tipo: P/D Duración: 2 hs
    Docente/s responsable/s: Nestor Alberto Calvo
    Descripción:
    Observaciones:

    Laboratorio de Informática

    Guías de actividades

    Actividad Título Descripción Descargar

    Requerimientos para regularizar

    Actividades Prácticas aprobadas antes de finalizar el cuatrimestre.

    Las prácticas se pueden realizar en conjunto pero la calificación surge de un coloquio individual donde se evalúa la comprensión de los métodos utilizados.

    Requerimientos para promover

    Aprobar además un coloquio integrador de las prácticas realizadas y los conceptos de teoría subyacentes.

    Entregar y defender un proyecto final libre, teórico o práctico, con un tema previamente consensuado con la cátedra. Puede realizarse en grupo con las mismas condiciones que el resto de las prácticas.

    Examen final

    Alumnos regulares

    Coloquio integrador de todas las prácticas realizadas y los conceptos de teoría subyacentes.
    Alumnos libres

    7 o más dias antes de la fecha de exámen: Entrega de prácticas adeudadas o no aprobadas y del proyecto final.

    En la fecha y horario del exámen: Coloquio integrador de las todas las prácticas realizadas y los conceptos de teoría subyacentes.

    Evaluaciones

    Fecha Tipo Modalidad Descripción
    19-06-2018 Coloquio Oral Coloquio Final.

    Todos los temas.