El objetivo general de esta memoria es extender y mejorar una herramienta interactiva gráfica que permite al usuario definir y visualizar el proceso de generación de mallas geométricas en dos dimensiones, agregándole nuevos algoritmos de refinamiento de mallas, nuevas funcionalidades y mejorando las existentes. Inicialmente se tiene una aplicación que tiene la funcionalidad de mostrar y procesar una malla en dos dimensiones con un algoritmo de refinamiento/mejoramiento dado con ciertos criterios definidos por el usuario. Luego de analizar la aplicación existente, se decide rediseñar una parte de sus procesos, considerando características en su diseño como extensibilidad, y modularidad. Se decide hacer una interfaz para el usuario, desde cero, la que comunica con la nueva aplicación. Se agregan nuevas funcionalidades a la aplicación, tal como la selección de regiones para su posterior refinamiento. Un nuevo algoritmo de refinamiento es agregado a la aplicación. Como resultado se tiene una herramienta para visualizar y manejar mallas geométricas en dos dimensiones, que es poderosa, extensible, flexible y simple de usar, junto con nuevas funcionalidades y algoritmos, con respecto de la aplicación original.

No description available.

Ingeniero Civil en Computación / El modelamiento de problemas que requieren una solución aplicando métodos numéricos como el método de volúmenes finitos necesita una malla geométrica (discretización compuesta de celdas simples tales como triángulos en 2D y tetraedros en 3D) que represente de la mejor forma posible al dominio a estudiar. Un método de generación de mallas geométricas basado en octrees genera, en su proceso de refinamiento, cuboides que presentan a lo más un punto extra en cada arista, conocidos como elementos 1-irregulares, los cuales deben ser teselados en elementos finales. Las mallas mixtas estudiadas son teselaciones de Delaunay compuestas de 7 elementos coesféricos (todos sus vértices están en la superficie de una esfera) finales: tetraedro, cuboide, prisma, pirámide, complemento de tetraedro, prisma deformado y complemento de tetraedro deformado. Esta memoria se enfoca en el ámbito de teselaciones Delaunay sobre cuboides 1-irregulares para mallas mixtas en 3D con el objetivo de minimizar la cantidad de elementos usados en cada teselación, ya que esto afecta directamente el desempeño de un simulador. Se desarrollaron dos herramientas que facilitan el análisis de las teselaciones resultantes de cuboides 1-irregulares, generados por bisección (los puntos extra bisectan a las aristas) y generados por intersección (los puntos extra se ubican arbitrariamente). La primera herramienta desarrollada se encarga de la generación de datos y estadísticas que permiten analizar la teselación de cualquier cuboide 1-irregular y clasificar a qué tipo de poliedro corresponden sus elementos. Se implementó un algoritmo que permite encontrar una teselación Delaunay formada por elementos coesféricos sobre un conjunto de puntos arbitrarios, el cual fue aplicado posteriormente sobre los distintos cuboides estudiados. La segunda herramienta consiste en una aplicación GUI que permite la visualización de la teselación de cualquier cuboide 1-irregular generado por bisección especificando el tamaño del cuboide base, permitiendo interactuar independientemente con cada elemento final generado y visualizar su centroide y circuncentro. El análisis de las teselaciones de los cuboides 1-irregulares arrojó la identificación de 31 elementos coesféricos adicionales a los 7 elementos previamente conocidos, 17 en cuboides generados por bisección y 14 exclusivos de cuboides generados por intersección. Sin embargo, los 7 elementos originales representan la gran mayoría del total de apariciones en todos los cuboides estudiados: más del 95% en cuboides generados por bisección y cerca del 97% en el caso de intersección, donde además, menos del 0,07% corresponde a elementos encontrados exclusivamente en este caso. Al mismo tiempo, se realizó un análisis de las teselaciones de cuboides 1-irregulares generados por bisección bajo distintos criterios de tal manera de minimizar el número de elementos finales distintos permitiendo agregar arcos y caras interiores a la teselación obtenida. Por ejemplo, agregando caras interiores, cerca del 96,9% del total de apariciones corresponde a los 7 elementos originales. Además, se identifican proporciones óptimas del cuboide 1-irregular base para obtener teselaciones generadas por bisección que permiten la aplicación del método de volúmenes finitos. Todas las teselaciones son apropiadas si el cuboide 1-irregular tiene una razón entre su lado más largo y su lado más corto menor o igual a √2.

Magíster en Ciencias, Mención Computación / Ingeniero Civil en Computación / En el campo de la cosmología, los vacíos son regiones del espacio cuya densidad es nota- blemente menor que la densidad de fondo, abarcando distancias en el rango de 20 50 Mpc/h (1 Mpc/h ∼ 2,10 × 1019 km). Los primeros vacíos fueron descubiertos en los primeros 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. Múltiples esfuerzos han sido destinados al estudio de los vacíos cósmicos para una mejor com- prensión de las etapas tempranas y posterior evolución del universo a gran escala, mediante el refinamiento y validación de los modelos cósmicos actuales. La tarea de detectar vacíos, sin embargo, no es trivial y es subjetiva pues la definición de vacío es algo ambigua. Hasta el día de hoy diversos autores continúan investigando este campo, por ejemplo mediante el diseño de mejores algoritmos para detectarlos dentro de catálogos o surveys de galaxias. Considerando lo anterior, hemos desarrollado un algoritmo de detección de vacíos basado en teselaciones de Delaunay: el algoritmo DELFIN (DELaunay Edge Void FINder) que se caracteriza por ser robusto, eficiente y extensible (tanto en 2-d y 3-d), aplicable en grandes catálogos de galaxias. Hemos alcanzado estas características mediante modificaciones y ex- tensiones sobre el algoritmo de Hervías et al. publicado en 2014. Nuestro algoritmo comparte algunas similitudes elementales con otros trabajos, pero las teselaciones de Delaunay proveen mayor maleabilidad y mejor rendimiento. Además, hemos validado nuestro algoritmo tanto con datos artificiales como reales, evaluándonos frente a un algoritmo buscador de vacíos ya existente (Foster y Nelson, 2008), con resultados alentadores. Tanto la implementación 2-d como la implementación 3-d (bajo ciertos supuestos) corren en tiempo O(n log n), donde n es el número de galaxias. Finalmente, proponemos algunas áreas para futura investigación, a partir de las cuales este algoritmo se vería beneficiado, así como también algunas sugerencias sobre cómo abordar y resolver algunos problemas asociados.

Following thesis regards itself with Voronoi diagram creation in 3D using a graphics card. It focuses on and compares certain algorithms that construct the diagram when given set of points in space. For this purpose there have been two algorithms implemented.  First one creates Delaunay tetrahedralization using parallel splitting and flipping of present tetrahedra. Then it transforms it into a Voronoi diagram. The second algorithms utilizes planes to cut a mesh until required shapes are created.  Testing shows the advantages and disadvantages of these algorithms and their relative performance. Main takeaway from this work for these algorithms is the relative sensitivity of the second method to the use of inappropriate shape in relation to given set of points. For the other algorithm its slower start and relative unsuitability for use with smaller sets of points is apparent, but it is greatly optimized for big sets.

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.

Surface mesh generation is a critical component of the mesh generation process. The objective of the described effort was to determine if a combination of constrained Delaunay triangulation (for triangles), advancing front method (for quadrilaterals), curvature-based refinement, smoothing, and reconnection is a viable approach for discretizing a NURBS patch holding the boundary nodes fixed. The approach is significant when coupled with recently developed geometry specification that explicitly identifies common edges. This thesis describes the various techniques used to achieve the above objectives. Application of this approach to several representative geometries demonstrates that it is an effective alternative to traditional approaches.

No description available.

En esta tesis, el algoritmo de SLAM localización y mapeo simultáneoha sido integrado con técnicas de planificación, con el fin de obtener trayectorias para vehículos terrestres en ambientes exteriores. El algoritmo de SLAM permite que el vehículo obtenga una representación del ambiente en un mapa variante en el tiempo al que podrían asociarse múltiples capas de datos, donde estas capas pueden incluir información diversa tal como: presencia de obstáculos, pendiente o altura del terreno, tipo de suelo, etc. Este mapa es dividido en regiones con alta correlación interna utilizando técnicas de geometría altamente eficientes desde el punto de vista computacional, con estructuras de datos y abstracciones que permitan manejar grandes cantidades de información. Estas regiones a su vez son divididas logrando una resolución en dos niveles de la información. Una que se denomina global y divide a todo el mapa conocido, y otra local que fracciona cada una de esas regiones. Con esta representación del ambiente, o en forma simultánea con la adquisición de ésta, es posible hallar trayectorias mediante técnicas de planificación. Con este fin, se definen criterios que permitan utilizar en la plani-ficación las múltiples capas de información permitiendo la utili-zación de cualquier algoritmo existente para este propósito. Esta aproximación permite lograr un algoritmo que es más eficiente que cualquier algoritmo de planificación existente para ambientes en exploración como se enfrentan en aplicio-nes de SLAM. Finalmente, como ejemplo de la estrategia propuesta, se generan trayectorias a partir de un modelo cinemático de un vehículo de cuatro ruedas y una estrategia de control. Se elige la velocidad lineal deseada del vehículo y se observa la limitación en el ángulo de giro del volante, con el objetivo de evaluar el desempeño del mismo mediante simulaciones numéricas y datos experimentales. / In this thesis, the SLAM algorithm Simultaneous Localization and Mapping has been integrated with planning strategies in order to achieve trajectories for land vehicles in outdoor environments. The SLAM algorithm allows the vehicle to obtain a representation of the environment in a time varying map. This time varying map could contain multiple layers of information, where these layers may include many types of data such as obstacles, slope or height of the terrain, etc. The map is divided into regions that have a high correlation using computational geometry techniques, which are highly efficient from the computational point of view. Towards this end, data structures and abstractions which can handle a significant amount of data are defined. Additionally, these regions are divided achieving two levels of inform: global and local. At global level, the whole known map is divided and at local level, each region is partitioned. Either once the repre-sentation of the environment is achieved or simultaneously with this process, it is possible to find trajectories using planning techniques. Criteria are defined to make use of the multiple layers of information at the planning stage and a particular type of planning algorithm is used, but there is a wide range of possible algorithms. This approach allows to achieve an algorithm that is more efficient than any existing planning algorithm for environments under exploration. Finally, to exemplify the proposed strategy, a kinetic model of a carlike vehicle is used with a control strategy to obtain trajectories. In these trajectories, the speed of the vehicle is chosen roughly constant and the limits of the steering angle are observed. The performance of the whole scheme is assessed through numerical simulations and experimental data.

In this thesis, two distinct problems in data-driven computational science are considered. The main problem of interest is the multiobjective optimization problem, where the tradeoff surface (called the Pareto front) between multiple conflicting objectives must be approximated in order to identify designs that balance real-world tradeoffs. In order to solve multiobjective optimization problems that are derived from computationally expensive blackbox functions, such as engineering design optimization problems, several methodologies are combined, including surrogate modeling, trust region methods, and adaptive weighting. The result is a numerical software package that finds approximately Pareto optimal solutions that are evenly distributed across the Pareto front, using minimal cost function evaluations. The second problem of interest is the closely related problem of multivariate interpolation, where an unknown response surface representing an underlying phenomenon is approximated by finding a function that exactly matches available data. To solve the interpolation problem, a novel algorithm is proposed for computing only a sparse subset of the elements in the Delaunay triangulation, as needed to compute the Delaunay interpolant. For high-dimensional data, this reduces the time and space complexity of Delaunay interpolation from exponential time to polynomial time in practice. For each of the above problems, both serial and parallel implementations are described. Additionally, both solutions are demonstrated on real-world problems in computer system performance modeling. / Doctor of Philosophy / Science and engineering are full of multiobjective tradeoff problems. For example, a portfolio manager may seek to build a financial portfolio with low risk, high return rates, and minimal transaction fees; an aircraft engineer may seek a design that maximizes lift, minimizes drag force, and minimizes aircraft weight; a chemist may seek a catalyst with low viscosity, low production costs, and high effective yield; or a computational scientist may seek to fit a numerical model that minimizes the fit error while also minimizing a regularization term that leverages domain knowledge. Often, these criteria are conflicting, meaning that improved performance by one criterion must be at the expense of decreased performance in another criterion. The solution to a multiobjective optimization problem allows decision makers to balance the inherent tradeoff between conflicting objectives. A related problem is the multivariate interpolation problem, where the goal is to predict the outcome of an event based on a database of past observations, while exactly matching all observations in that database. Multivariate interpolation problems are equally as prevalent and impactful as multiobjective optimization problems. For example, a pharmaceutical company may seek a prediction for the costs and effects of a proposed drug; an aerospace engineer may seek a prediction for the lift and drag of a new aircraft design; or a search engine may seek a prediction for the classification of an unlabeled image. Delaunay interpolation offers a unique solution to this problem, backed by decades of rigorous theory and analytical error bounds, but does not scale to high-dimensional "big data" problems. In this thesis, novel algorithms and software are proposed for solving both of these extremely difficult problems.