Citation
Alonso Núñez, Guillermo
(2016).
Fitting plane tessellations through Voronoi diagrams = Ajuste de particiones planas mediante diagramas de
Voronoi.
Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S. de Ingenieros Informáticos (UPM), Madrid, España.
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.