VOLVER

Share

La Hispalense diseña un método óptimo para calcular cómo de separados están dos puntos

Fuente: Universidad de Sevilla


18 de junio de 2013
Clara Grima

Clara Grima

Miembros del Grupo de Investigación Matemática Discreta: Teoría de Grafos y Geometría Computacional de 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… en un barrio o zona determinada de una ciudad.

La catedrática de Escuela Universitaria de Matemática Aplicada de la US Clara Grima 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: http://www.worldscientific.com/doi/abs/10.1142/S0218195912500100

 

 


Share

Últimas publicaciones

Desarrollan un material sencillo y desordenado que descontamina el aire con la luz del sol
Córdoba | 19 de noviembre de 2026

Una investigación, realizada en el Instituto Químico para la Energía y el Medioambiente (IQUEMA) de la Universidad de Córdoba y en colaboración con la Universidad de Málaga, ha diseñado un material que, gracias a la luz, es capaz de reducir del ambiente uno de los gases más contaminantes generados en la industria y por la quema de combustibles fósiles y tráfico rodado, los llamados óxidos de nitrógeno.

Sigue leyendo
Comprueban que la estadística clásica iguala a la IA para estimar riesgo de cáncer de tiroides
Cádiz | 18 de noviembre de 2026

Un equipo de investigadores de la Universidad de Cádiz, del Hospital Universitario de Puerto Real, perteneciente al Servicio Andaluz de Salud (SAS) de la Consejería de Presidencia, Sanidad y Emergencias, y del Instituto de Investigación e Innovación Biomédica de Cádiz (INIBICA) ha comprobado que el uso de una fórmula estadística clásica, sencilla y transparente puede igualar a los algoritmos de inteligencia artificial en la estimación del riesgo de padecer cáncer de nódulos tiroideos.

Sigue leyendo
Desarrollan un método para reconstruir digitalmente muros prehistóricos a partir de escaneado láser 3D
Sevilla | 18 de noviembre de 2026

Un equipo de la Universidad de Sevilla, liderado por el profesor del Departamento de Expresión Gráfica e Ingeniería en Edificación Juan José Moyano, ha desarrollado un método computacional para reconstruir digitalmente la geometría de antiguas construcciones a partir de los restos arqueológicos que han llegado hasta nuestros días.

Sigue leyendo

#CienciaDirecta

Tu fuente de noticias sobre ciencia andaluza

Más información Suscríbete

Ir al contenido