VOLVER

Share

Diseñan un método óptimo para calcular cómo de separados están dos puntos

Fuente: Universidad de Sevilla


22 de marzo de 2013

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.


Share

Últimas publicaciones

Desarrollan un modelo para reducir fugas de agua en las redes de distribución a partir de datos de los cambios de presión
Córdoba | 01 de julio de 2025

El modelo de control, ideado por un equipo de la Universidad de Córdoba, permite reducir el desperdicio de un recurso esencial y limitado y alargar la vida útil de las tuberías. El modelo predictivo resultante, escalable a otras redes similares, permite superar una gran limitación que encuentran las empresas gestoras de redes de distribución de agua, como es la ausencia de datos en tiempo real que las orienten a la hora de realizar ajustes dinámicos de la presión.

Sigue leyendo
Crean un sistema que reduce la temperatura en naves de ganado vacuno y se consigue mayor productividad de leche
Córdoba | 30 de junio de 2025

El bienestar animal así como un mayor rendimiento en cantidad y calidad han sido parte de los objetivos de este proyecto que ha contado como socios a COVAP, CETEMET, Keyter, Universidad de Córdoba y Cooperativas Agro-alimentarias de Andalucía.

Sigue leyendo
Demuestran la viabilidad de vinos con menor graduación alcohólica preservando la calidad del producto
Córdoba | 30 de junio de 2025

El grupo operativo INNOFINO, formado por el Consorcio ceiA3 junto a las universidades de Cádiz y de Córdoba, varios consejos reguladores andaluces así como distintas bodegas del marco de Jerez, acaban de presentar los resultados finales del proyecto en la Consejería de Agricultura, Pesca y Desarrollo Rural de la Junta de Andalucía en Sevilla. 

Sigue leyendo

#CienciaDirecta

Tu fuente de noticias sobre ciencia andaluza

Más información Suscríbete

Ir al contenido