Diseñan un método óptimo para calcular cómo de separados están dos puntos
Fuente: Universidad de Sevilla
Miembros del Grupo de Investigación Matemática Discreta: Teoría de Grafos y Geometría Computacionalde la Universidad de Sevilla han diseñado un algoritmo que requiere n² operaciones para calcular cómo de separados o intrincados están dos colecciones de puntos (digamos unos puntos rojos y otros azules, que pueden representar ciertas características de elementos de dos conjuntos distintos).
En la práctica, este tipo de operaciones matemáticas son muy útiles a la hora de establecer, por ejemplo, la distribución de servicios como oficinas de correos, farmacias, hospitales, colegios, supermercados, etc., en un barrio o zona determinada de una ciudad.
La Catedrática de Escuela Universitaria (CEU), Clara Grima Ruiz, explica que esta investigación presenta una variación natural del problema de computar todas las intersecciones bicromáticos entre dos conjuntos de segmentos. Dados dos conjuntos R y B de n puntos en el plano que define dos conjuntos de segmentos, por ejemplo rojo y azul, se presenta un O (n2) y el algoritmo de espacio para resolver el problema de cuántos segmentos de cada color son intersectados por segmentos del otro color. También demuestran que este problema es el 3-Sum y proporciona algunos ejemplos que ilustran las diversas configuraciones puntuales.
Este avance matemático es interesante tanto en problemas de clasificación de objetos, como en problemas de visibilidad.
“Una medida de ello es la siguiente: consideramos todos los segmentos con extremos puntos rojos y todos los segmentos con extremos puntos azules y contamos cuántos de los primeros (y de los segundos) son atravesados por algún segmento del otro color. Cuanto mayor sean estos números, más entremezclados están los puntos. Una forma de calcular dichos números sería representando todos los segmentos y después contando las intersecciones, pero ello nos llevaría a un algoritmo que requeriría n⁴ operaciones (que puede llevar mucho tiempo, aún en ordenadores potentes, si el número n es muy alto). Nosotros hemos diseñado un algoritmo que requiere n² operaciones (para comprender la diferencia si n=1.000, n² es un millón y n⁴ un billón), además hemos probado que el problema es 3-Sum-hard lo cual viene a demostrar que, en la práctica, nunca se diseñará un algoritmo mejor que n², en otras palabras: que nuestro método es óptimo”, afirma Grima.
Este conjunto de expertos se encuentra inmerso también en otra línea de investigación sobre el modelado cuántico de redes sociales.
Más información.
Últimas publicaciones
El próximo 12 de agosto, al atardecer, las miradas de curiosos y aficionados a la astronomía apuntarán al cielo. El primero de los tres eclipses que se sucederán en 2026, 2027 y 2028 se iniciará a las 19:39, y llegará a su fase máxima hacia las 20:30, para finalizar entre las 21:15 y 21:25, dependiendo de la zona dónde se observe. En Andalucía se observará de forma parcial, y aunque el Sol no esté totalmente oculto, los expertos recomiendan protección ocular con gafas homologadas, evitar trucos caseros y poco efectivos como gafas de sol convencionales, radiografías, CD o cristales ahumados, ir debidamente equipados con agua y ropa de abrigo, así como escoger lugares abiertos y seguros, siempre mirando al horizonte occidental despejado.
Investigadores de las universidades de Almería y Granada han identificado en varios puntos cercanos a la capital almeriense afloramientos de origen marino correspondientes a la época geológica previa en la que el Mediterráneo se secó casi por completo. En estos arrecifes formados a casi 40 metros bajo el nivel del mar, la transparencia del agua en ese entorno facilitó el crecimiento de corales de lado a lado. Ahora aportan pistas para reconstruir la historia climática del pasado.
Un equipo de investigación de la Universidad de Málaga ha diseñado una estrategia de control para motores utilizados en movilidad eléctrica y aeronáutica. Esta técnica mejora la calidad de la corriente y predice el funcionamiento más adecuado, optimizando su eficiencia de consumo y respondiendo ante posibles fallos.
