A robust void-finding algorithm using computational geometry and parallelization techniques

• Main Author: Schkolnik Müller, Demian Aley
• Other Authors: Bustos Cárdenas, Benjamín, Hitschfeld Kahler, Nancy, Cerda Villablanca, Mauricio, Navarro Badino, Gonzalo, Marín Caihuan, Mauricio
• Format: Thesis
• Language: English
• Published: Universidad de Chile 2018
• Subjects: Algoritmos computacionales; Triangulación; Astronomía; Triangulación Delaunay; Void finder; Baja; Lambda; Orca
• Online Access: https://repositorio.uchile.cl/handle/2250/168498

Tesis para optar al grado de Magíster en Ciencias, Mención Computación El modelo cosmológico actual y más aceptado del universo se llama Lambda Cold Dark Matter. Este modelo nos presenta el modelo más simple que proporciona una explicación razonablemente buena de la evidencia observada hasta ahora. El modelo sugiere la existencia de estructuras a gran escala presentes en nuestro universo: Nodos, filamentos, paredes y vacíos. Los vacíos son de gran interés para los astrofísicos ya que su observación sirve como validación para el modelo. Los vacíos son usualmente definidos como regiones de baja densidad en el espacio, con sólo unas pocas galaxias dentro de ellas. En esta tesis, presentamos un estudio del estado actual de los algoritmos de búsqueda de vacíos. Mostramos las diferentes técnicas y enfoques, e intentamos deducir la complejidad algorítmica y el uso de memoria de cada void-finder presentado. Luego mostramos nuestro nuevo algoritmo de búsqueda de vacíos, llamado ORCA. Fue construido usando triangulaciones de Delaunay para encontrar a los vecinos más cercanos de cada punto. Utilizando esto, clasificamos los puntos en tres categorías: Centro, borde y outliers. Los outliers se eliminan como ruido. Clasificamos los triángulos de la triangulación en triángulos de vacíos y centrales. Esto se hace verificando un criterio de distancia, y si los triángulos contienen outliers. Este método nos permite crear un algoritmo de búsqueda de vacíos rápido y robusto. Adicionalmente, se presenta una versión paralela del algoritmo.