Queries about the largest empty rectangle in large 2-dimensional datasets stored in secondary memory

Consultas sobre el rectángulo vacío de mayor área en grandes conjuntos de datos de dos dimensiones, almacenados en memoria secundaria

Sea S un conjunto de puntos ubicado en un rectángulo R, y q un punto que no está en S.- Este artículo describe el diseño, la implementación y experimentación de diferentes algoritmos para resolver los siguientes problemas: (i) MER, que consiste en encontrar un rectángulo vacío de máxima área contenido en R y que no contiene un punto de S, y (ii) QMER, que consiste en encontrar un rectángulo con las mismas restricciones dadas para el problema MER y que, además, debe contener a q. En ambos problemas se asume que no existe suficiente memoria para almacenar todos los objetos del conjunto S. De acuerdo con la literatura, ambos problemas son de mucha utilidad práctica, en ámbitos como la minería de datos, sistemas de información geográfica, por nombrar algunos. Concretamente, en este trabajo se proponen dos algoritmos que asumen que S se encuentra almacenado en memoria secundaria y que no es posible almacenarlo completamente en memoria. El primero resuelve el problema QMER y consiste en disminuir el tamaño de mediante la utilización de zonas de dominancia y luego, mediante un algoritmo propuesto por Orlowski (1990), se procesan los puntos no descartados. El segundo, a su vez, resuelve el problema MER y consiste en dividir R en cuatro subrectángulos generando cuatro subconjuntos de similar tamaño los que se procesan mediante un algoritmo propuesto en Edmonds et al. (2003), combinando finalmente las soluciones parciales para obtener la solución global. Con el objeto de verificar la eficiencia de los algoritmos, se muestran los resultados de una serie de experimentos considerando datos sintéticos y reales.

Introducción

La geometría computacional es un área de las matemáticas que estudia y propone soluciones algorítmicas a problemas geométricos. Es un área relativamente nueva y los primeros resultados se remontan a los años 80. Sean S₁ y S₂ dos conjuntos de puntos situados en las regiones R₁⊆ R^d (típicamente d = 2) y R₂ ⊆ R^d , respectivamente. Algunos de los problemas estudiados con geometría computacional son (i) encontrar el casco convexo de S₁, (ii) dado un punto q no perteneciente a S₁ y un parámetro k> 0, encontrar los k puntos de S1 más cercanos a q, (iii) dado un parámetro k> 0, encontrar los k pares de puntos (uno de S₁ y otro de S₂) cuyas distancias (distancia euclidiana) son las más cortas entre todos los pares posibles que se pueden formar, y (iv) dado un punto q no perteneciente a S₁, encontrar el rectángulo vacío de mayor área incluido en R₁.