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

Aplican la ciencia ciudadana para reducir el tiempo de uso del móvil en jóvenes andaluces
Sevilla | 28 de mayo de 2024

Investigadores de las Universidades de Sevilla, Jaén y Cádiz participan en el proyecto ‘Desconéctate para Conectar: Fomentando un Estilo de Vida Activo y Saludable entre los Jóvenes Andaluces’ que buscará estrategias concretas para incentivar a estudiantes de secundaria, bachillerato y universidad a que cambien sus hábitos de uso de dispositivos móviles por actividades físicas.

Sigue leyendo
Descubren un nuevo gen que hace resistente al girasol contra la planta parásita jopo
Córdoba | 27 de mayo de 2024

Un equipo de investigación del Instituto de Agricultura Sostenible (IAS-CSIC) ha descrito una pieza del ADN que impide que las raíces de este cultivo sean infectadas por uno de sus patógenos más letales, el jopo. Además de determinar su posible función y la localización en su genoma, ha demostrado la posibilidad de transferirlo como mecanismo natural de defensa desde una especie silvestre a otras variedades de siembra.

Sigue leyendo
Un estudio del CSIC revela que zorzales, codornices y pinzones son las especies de aves más propensas a tener garrapatas
Sevilla | 27 de mayo de 2024

Un nuevo estudio liderado por la Estación Biológica de Doñana – CSIC ha analizado la prevalencia de garrapatas en más de 600.000 aves capturadas a lo largo de 17 años. Los resultados podrán ayudar a identificar en qué especies se deberían focalizar los esfuerzos de vigilancia de enfermedades zoonóticas. Los resultados de este trabajo se han publicado en la revista One Health.

Sigue leyendo

#CienciaDirecta

Tu fuente de noticias sobre ciencia andaluza

Más información Suscríbete

Ir al contenido