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.
Artículo:
Reflexiones sobre la gestión tecnológica en las cadenas de suministro
Artículo:
Innovación, desarrollo de nuevos productos y tecnologías de Internet: estudio en empresas brasileñas
Artículo:
Servicio de M-comercio. Sistema de interacción entre un centro comercial y sus visitantes utilizando las tecnologías WAP y Bluetooth
Video:
Entrevistas de programación: problema de cambio en monedas (programación dinámica)
Artículo:
Desarrollo del sistema motriz virtual de una plataforma subacuática móvil inspirada en biomimetismo
Artículo:
Creación de empresas y estrategia : reflexiones desde el enfoque de recursos
Artículo:
Importancia, manejo y control de extraíbles e incrustaciones (pitch) en la fabricación de papel
Libro:
Tratamientos avanzados de aguas residuales industriales
Artículo:
Estudio sobre la evaluación de la sostenibilidad de los productos innovadores