Árbol generador euclídeo de longitud y diámetros cortos

Resumen

En este trabajo se plantea el problema de conectar n puntos del plano mediante
un grafo conexo que tenga tanto su longitud como su diámetro lo más peque~nos
posible.
Se consideran grafos geométricos cuyos vértices son puntos del plano y cuyas
aristas son segmentos rectilíneos que tienen por extremos dos vértices. La longitud
de un grafo es la suma de las longitudes de sus aristas. La distancia entre dos vértices
del grafo es la suma de las longitudes de las aristas del camino más corto que los
conecta. El diámetro de un grafo es la mayor de las distancias entre dos de sus
vértices.
Está claro que el grafo de longitud mínima que conecta n puntos no contiene ciclos
y, por tanto, se trata de un árbol. Si solo se considera esta condición, la solución
la da el árbol generador euclídeo mínimo (EMST, Euclidean Minimum Spanning
Tree en inglés). Sin embargo, el diámetro del EMST, como se verá en la memoria,
puede ser muy grande. Por otra parte, si solo se considera la condición del diámetro
mínimo, la solución será el árbol generador de diámetro mínimo (MDST, Minimum
Diameter Spanning Tree en inglés) del que se conocen, como en el caso del EMST,
algoritmos eficientes para su cálculo. Este cómputo se desarrollará en SAGE, un
entorno de cálculos matemáticos (MCE { Mathematics computing enviroment) de
código abierto, y usará una estructura para definir grafos planos llamada DCEL
(lista de aristas doblemente enlazada).
Al combinar las dos condiciones se plantea un problema de minimización biparamé
trico para el que no se conocen soluciones. De hecho, no puede decirse que
exista una solución óptima pues cada uno de estos criterios puede perjudicar al otro.
En el trabajo se empieza haciendo un estudio estadístico del diámetro del EMST
de conjuntos aleatorios de puntos que confirma que, en general, el EMST no es el
árbol de diámetro mínimo que conecta los puntos. A continuación, se emplea la
triangulación de Delaunay y algunos de sus subgrafos notables - el grafo de Gabriel
y el de vecindad relativa (RNG, Relative Neighbour Graph en inglés)- como técnica
para buscar una solución de equilibrio entre longitud y diámetro cortos. La técnica
consiste en calcular, para los mencionados grafos, el árbol generador de diámetro
mínimo. Se completa el trabajo con el análisis experimental de las soluciones propuestas.---ABSTRACT---This work presents the problem of connecting n points in the plane by a connected
graph that has both its length and diameter as small as possible.
Geometric graphs whose vertices are points in the plane and whose edges are
rectilinear segments connecting vertices are considered. The length of a graph is the
sum of the lengths of all edges. The distance between two vertices is the length of
their shortest path in the graph. The diameter is the longest distance between any
two vertices in the graph.
It is clear that the graph of minimum length that connects n points does not contain
cycles and, therefore, is a tree. If only this condition is considered, the solution
to the problem is given by Euclidean Minimum Spanning Tree (EMST). However,
the diameter of EMST, as will be seen in the work, can be very large. Moreover, if
only the condition of minimum diameter is considered, the solution would be the
Minimum Diameter Spanning Tree (MDST) for which eficient algorithms that compute
it are known, similar to the EMST case. This operation will be carried out in
SAGE, a free open source Mathematics computing enviroment (MCE), and it will
use a DCEL (Doubly Connected Edge List) structure to define planar graphs.
Combining the two conditions mentioned, a biparametric minimization problem
with no known solutions arises. In fact, it cannot be stated that there exists an
optimal solution, since the individual growth of one parameter may harm the other.
This work begins performing a statistical study about the diameter of EMST
with random point sets that confirms that, generally, EMST is not the minimum
diameter tree. Then, it uses the Delaunay Triangulation and some of its important
subgraphs - the Gabriel Graph and the Relative Neighbour Graph (RNG) - as a
technique to find a balanced solution between short length and short diameter.
The procedure involves calculating, for the above graphs, the Minimum Diameter
Spanning Tree. To conclude, it presents experimental tests of the proposed solutions.