Fitting plane tessellations through Voronoi diagrams = Ajuste de particiones planas mediante diagramas de Voronoi

Abstract

Los diagramas de Voronoi tienen aplicaciones tanto prácticas como teóricas en muchos ámbitos, la mayoría relacionados con la ciencia y tecnología, aunque también se aplican en otros campos como el arte visual. El objetivo de éste proyecto es estudiar el problema inverso del diagrama de Voronoi y diseñar, comparar y analizar diferentes estrategias para su resolución. Dicho problema consiste en detectar si una partición dada es o no un diagrama de Voronoi, y en caso afirmativo, calcular las semillas que lo generan. Para particiones que no lo son, sería interesante encontrar el diagrama de Voronoi que mejor se aproxima. Para ello, necesitaremos algún método para poder conocer la calidad de una solución y poder comparar varias soluciones. Usaremos la diferencia simétrica para tal fin. Nótese que el número de soluciones candidatas es infinito dado que se trata de un espacio de búsqueda continuo. Probar todas ellas y elegir la mejor es por tanto inviable. Por tanto, trataremos de resolver el problema mediante diferentes metaheurísticas, es decir, trataremos de hallar la solución óptima, aunque no podremos asegurar que la solución dada sea óptima. El esquema básico de todas las estrategias es el siguiente: - Para cada entrada, calcular un conjunto de puntos semilla a partir de los cuales comenzaremos la búsqueda. - Desplazamos los puntos ligeramente según algún criterio y comprobamos si hemos conseguido mejorar nuestra solución, actualizando ésta en ese caso. - Repetimos el paso anterior hasta que no podamos seguir mejorando o hasta que la solución obtenida se considere lo suficientemente buena. El ajuste de una partición del plano mediante diagramas de Voronoi es útil para resolver problemas de optimización a la hora de colocar objetos con restricciones espaciales. Un ejemplo es el problema de colocar colegios atendiendo a los diferentes distritos escolares. La Figura 0.1(a) muestra los diferentes distritos escolares en Tsukuba (los círculos muestran la ubicación de los institutos). En Japón, los estudiantes de un distrito deben ir al colegio asignado a ese distrito. Como resultado, en algunas áreas los estudiantes tienen que ir a un colegio que no es el más cercano. Si asumimos que los estudiantes pueden llegar al colegio siguiendo el camino Euclidiano, en la Figura 0.1, las zonas en las que los estudiantes no pueden ir al colegio más cercano aparecen sombreadas en la Figura 0.1(a), donde los polígonos se corresponden con el diagrama de Voronoi generado por la posición de los institutos. El problema consiste en reubicar los colegios de forma que el número de estudiantes que no pueden ir al colegio más cercano es mínima. La Figura 0.1(b) muestra una colocación óptima local obtenida por Suzuki e Iri (1986a). La proporción de área de estudiantes que no pueden ir al instituto más cercano se reduce de un 20% a un 10%.---ABSTRACT---Voronoi diagrams have practical and theoretical applications to a large number of fields, mainly in science, technology and visual art. The aim of this project is to study the inverse Voronoi diagram problem and design, compare and analyze different strategies for its resolution. The inverse Voronoi diagram problem consists on detecting whether a given plane tessellation is a Voronoi diagram and finding the seed points that would generate such a tessellation. For a tessellation which does not come from a Voronoi diagram, it would be interesting to find the best fitting Voronoi diagram. At this point, we need a way to measure how good a candidate solution is. We will be using the total symmetric difference between the two tessellations for that. Note that despite the search space is bounded, it being continuous grants an infinite number of solution candidates. Therefore, we will try to solve the problem using different metaheuristics, that is, we will try to look for the optimal solution. However, we will not be able to assure whether the obtained solution is optimal. The basic steps of all the strategies are: - For each input, calculate a set of seed points from which we will start. - Move each point slightly following some criteria and check if we improved the current best solution. - Repeat last step until we cannot keep improving or we are satisfied with the result. The method of fitting a Voronoi diagram to a given tesellation is also useful to solve the locational optimization of facilities whose use is spatially restricted. An example is the locational optimization of schools constrained by school districts. Figure 0.1(a) shows the districts of junior high schools in Tsukuba (the filled circles indicate the locations of the schools). In Japan, students in a school district are supposed to go to the school assigned to that district. As a result, students in some areas have to go to a school which is farther than the nearest school. If we assume that students can take the Euclidean path in Figure 0.1, the area in which students cannot go to their nearest schools is given by the hatched region in Figure 0.1(a), where the polygons are the Voronoi diagram generated by the school sites. The locational optimization problem is to relocate the schools so that the number of students who cannot go to their nearest schools is minimized. Figure 0.1(b) shows the locally optimal locations obtained by Suzuki and Iri (1986a). The area in which students cannot go to their nearest schools reduces from 20% to 10% by this relocation.