Optimización de un algoritmo para encontrar vacíos poligonales en un conjunto de puntos en el plano

Abstract

En el campo de la cosmología, los espacios vacíos se definen como regiones del espacio cuya densidad es notablemente menor que la densidad de fondo, abarcando distancias en el rango de 20 a 50 Mpc/h. Los espacios vacíos fueron descubiertos en los catálogos sistemáticos de galaxias lejanas a fines de la década de 1970. Sus propiedades han sido reconocidas como críticas para la comprensión de la estructura a gran escala del universo. Existen actualmente varias herramientas computacionales para el estudio de los vacíos cósmicos para un mejor entendimiento de la evolución del universo a gran escala refinando y validando modelos cósmicos actuales. Sin embargo, la tarea de detectar espacios vacíos no es trivial y es subjetiva ya que la definición de vacío es algo ambigua. En la actualidad varios autores continúan investigando este tema y un ejemplo de esta investigación es el diseño del algoritmo DELFIN el cual consiste en buscar espacios vacíos en un conjunto de puntos usando la triangulación de Delaunay y clasifica los candidatos a vacíos por criterios como el área o por el arco más largo. Este algoritmo tiene una segunda versión conocida como DELFIN EXTENDIDO, la cual incluye a DELFIN mas la unión de subvacíos encontrados por el largo del arco que los une. Los espacios vacíos no solamente se presentan en el universo, también se puede presentar en otros ámbitos como en la células, en un conjunto de datos que pertenecen a una clasificación, en estadísticas que utilizan gráfico de puntos y en cualquier otro ámbito donde se pueda presentar un vacío. El algoritmo DELFIN EXTENDIDO busca espacios vacíos dado un conjunto de puntos donde es necesario usar cálculos geométricos como la triangulación de Delaunay, obtener el área de un polígono y la distancia entre dos puntos. Existe una librería llamada CGAL, que permite programar estos cálculos geométricos mencionados y muchos otros cálculos. Por lo que es interesante evaluar si el uso esta librería nos permitiría disponer de una implementación mas precisa, eficiente y robusta. En esta tesis se ha implementado un algoritmo que encuentra espacios vacíos usando la triangulación de Delaunay creados a partir de un conjuntos de puntos en el plano de dos dimensiones, utilizando por primera vez la librería CGAL, una librería geométrica robusta y eficiente, la cual optimiza el algoritmo debido a que cuenta con estructura de datos y algoritmos que facilitan la implementación y el tiempo de ejecución del algoritmo. Esta implementación es llamada Delfin ++ debido a que usa el lenguaje de programación C++. Delfin ++ tiene los mismos pasos que el algoritmo DELFIN EXTENDIDO, teniendo como criterio de clasificación para los vacíos encontrados su área o su arco más largo y como unión de vacíos el criterio el arco que los une. Finalmente se probó Delfin ++ donde los vacíos que se formaron son circulares e irregulares. También se hizo una comparación de complejidad algorítmica, tiempo de ejecución y memoria consumida con el último algoritmo implementado el cual se resume con el nombre de Delfin extendido. Los resultados favorecen al Delfin ++ en memoria consumida, pero mantiene la complejidad algoritmica del Delfin extendido y lo favorece en tiempo de ejecución para grandes volúmenes de datos ya que Delfin ++ se comporta de manera lineal de acuerdo a la cantidad de triángulos generados en la triangulación de Delaunay. Aunque Delfin ++ no mejora por completo a Delfin extendido selogró hacer pruebas con datos reales financieros y tener conclusiones del comportamiento de estos datos por medio de los vacíos encontrados, permitiéndonos utilizar el algoritmo DELFIN EXTENDIDOno solamente en el ámbito científico, sino en cualquier ámbito que pueda ser medido y cuantificado.