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 S1 y S2 dos conjuntos de puntos situados en las regiones R1⊆ Rd (típicamente d = 2) y R2 ⊆ Rd , respectivamente. Algunos de los problemas estudiados con geometría computacional son (i) encontrar el casco convexo de S1, (ii) dado un punto q no perteneciente a S1 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 S1 y otro de S2) 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 S1, encontrar el rectángulo vacío de mayor área incluido en R1.
Esta es una versión de prueba de citación de documentos de la Biblioteca Virtual Pro. Puede contener errores. Lo invitamos a consultar los manuales de citación de las respectivas fuentes.
Video:
Haciendo analítica de datos masivos interactiva y en tiempo real
Artículo:
La influencia de la integración de los proveedores y la adopción de prácticas ajustadas en el rendimiento operativo
Artículo:
Plataforma virtual como mecanismo de e-gobierno entre la población joven y la administración local de Mosquera, Colombia
Tesis:
Diseño de planta de una instalación de empaque para líquidos que incluya buenas prácticas de manufactura y manufactura esbelta
Artículo:
Diseño de un duplexor de gran ancho de banda en tecnología de guía de onda para aplicaciones de satélite