Implementación en java de algoritmos geométricos sobre grandes conjuntos de datos

Abstract

La Geometría Computacional es un área de las matemáticas que se ocu- pa de estudiar y proponer soluciones algorítmicas a problemas geométricos. Es un área muy joven, pues sus primeros resultados se pueden apreciar en la década del 80. Sea S1 y S2 conjuntos de puntos ubicados en regiones R1 ⊆ Rd (típicamente d = 2) y R2 ⊆ Rd respectivamente, algunos de los problemas estudiados por la Geometría Computacional son: (i) encontrar la cerradura convexa de S1, (ii) dado un punto q ∈/ S1 y un parámetro k > 0, encontrar los k-puntos de S1 más cercanos a q, (iii) dado un parámetro k > 1 encontrar los k pares de puntos (uno de S1 y el otro de S2) cuyas distancias sean las menores de entre todos los posibles pares que se puedan formar (iv) dado un punto q ∈/ S1 encontrar el rectángulo vacío de mayor área incluido en R1. La utilidad de contar con soluciones algorítmicas para estos problemas está muy bien establecida en la literatura.

Las soluciones a los problemas geométricos, desde la Geometría Compu- tacional, suponen que es posible almacenar todos los objetos en la memoria de un computador. Sin embargo, con la aparición de grandes conjuntos de datos espaciales, se ha hecho necesario extender o crear soluciones que asu- man que los datos se encuentran en estructuras de datos multidimensionales residentes en memoria secundaria (principalmente disco). En este contexto, las operaciones que predominan o determinan la eficiencia de un algoritmo corresponden a operaciones de entrada/salida o accesos a bloques de disco, las cuales son muy costosas en tiempo. Actualmente, existen soluciones para varios de los problemas indicados arriba. Por ejemplo, suponiendo que el conjunto de puntos se encuentra almacenado en un R-tree, el cual es una es- tructura de datos tipo árbol similar al B-tree, el R-tree está diseñado para la indexación dinámica de un conjunto de objetos geométricos k-dimensional. [1], en [2] se propone un algoritmo que resuelve el problema (i), en [3] se des- cribe un algortimo para el problema (ii), en [4, 5, 7] se aportan algoritmos para el problema (iii) y en [7, 8] se proponen soluciones para una variante del problema (iv).

En este informe se describe la implementación de un algortimo para una variante del problema (iv) propuesto en [6] y que llamaremos MER (Maxi- mal Empty Rectangle). Informalmente, el problema MER consiste en dado un conjunto de puntos S localizados en una región R ⊆ R2 , encontrar todos los rectángulos vacios, maximales y que estén contenidos en R. El algorit- mo considera el escenario en que los puntos se encuentran almacenados en un archivo sin formato (raw file). También se describe en este informe la implemantación de una variante MER, y que llamamos qMER (Query Ma- ximal Empty Rectangle) y que consiste en dado un conjunto de puntos S localizados en una región R ⊆ R2 y un punto q ∈/ S encontrar el rectángulo maximal, de mayor área y que solo contine a q y que esté contenido en R. La utilidad de contar con soluciones para MER y qMER considerando grandes volúmenes de datos se pueden encontrar en [6] y [7, 8] respectivamente.