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

Diseñan láminas impresas en 3D para reducir hasta cuatro veces los daños de las fresas durante el transporte
Córdoba | 21 de noviembre de 2026

Un equipo de investigación de la Universidad de Córdoba ha desarrollado un recubrimiento plástico que amortigua las vibraciones y los impactos dentro del empaquetado. La solución disminuye los golpes que recibe el fruto tanto en ensayos de laboratorio como en recorridos reales en caminos rurales.

Sigue leyendo
Neuromarketing para analizar cómo los jóvenes procesan campañas de igualdad
Málaga | 20 de noviembre de 2026

¿Cómo reciben los menores y adolescentes los mensajes publicitarios que promueven la igualdad de género? ¿Es suficiente con despertar una emoción o es necesario que comprendan también la causa social que transmite la campaña? Estas son algunas de las cuestiones que aborda una investigación liderada por la UMA que utiliza el neuromarketing como herramienta de análisis.

Sigue leyendo
Acogen 300 salinetes para contribuir a la conservación de este pez endémico de Andalucía
Sevilla | 20 de noviembre de 2026

La Universidad Pablo de Olavide se ha incorporado al Programa de Conservación del Salinete y Fartet de la Junta de Andalucía, una iniciativa que busca frenar el declive de estas dos especies de peces amenazadas y recuperar sus poblaciones en el medio natural. En el marco de esta colaboración, la Consejería de Sostenibilidad y Medio Ambiente ha autorizado la cesión a la UPO de 300 ejemplares de salinete (Aphanius baeticus), un pequeño pez que solo vive en Andalucía y cuyas poblaciones se encuentran en franco retroceso.

Sigue leyendo

#CienciaDirecta

Tu fuente de noticias sobre ciencia andaluza

Más información Suscríbete

Ir al contenido