Algoritmo para la resolución física en tiempo lineal del problema de los n-cuerpos en colonias de bacterias

Abstract

Con el fin de conocer mejor las dinámicas bacterianas, se han desarrollado aplicaciones que permiten simular los comportamientos que se encuentran en las colonias de éstas. Una pieza de gran importancia en estas simulaciones es el motor físico. Éste es el encargado de emular y resolver todas las interacciones físicas que ocurren en las colonias, llevándose gran parte del cómputo total del simulador. En una simulación de estas características, todas las bacterias crecen en un espacio falto de libertad, dificultando en gran medida su resolución mediante los métodos habituales. Este es un problema que se enmarca dentro de los problemas de los n-cuerpos cuya solución tiene un coste computacional de O(N2 ). En este trabajo se presenta un nuevo algoritmo, llamado Pushing by Rings, que permite la resolución de este tipo de problemas en O(N). El objetivo de esta aproximación es liberar la carga computacional que requiere el motor físico con el fin de lograr simular poblaciones de bacterias muy elevadas en poco tiempo.---ABSTRACT---Many applications have been developed with a focus kept on extracting knowledge about bacterial dynamics. The aim of these applications is to simulate behaviors that are found in bacterial colonies. An important piece in these simulations is the physics engine. It is responsible for emulating and resolving all physical interactions that arise in the colony, carrying the largest part of the computation cost within a simulator. In this type of simulations, the entire population grows in a space lacking freedom, hindering its resolution by usual methods. This problem lies in the class of n-body problems, whose solution has a cost of O(N2 ). In this work, a novel algorithm called Pushing by Rings is proposed. It allows the resolution of n-body problems applied to bacterial colonies with a computational cost of O(N). The aim of this approach is to make the computational load of the physical engine lighter, with the purpose of simulating high populations in less time.