Fahad Zulfiqar MSc Dissertation 2015/16

Implementation of a Tree-based algorithm for Contact Detection

Supervised by D.Walker

Abstract

It is possible to simulate a population of growing biological cells by representing each as a circle

(or sphere in 3D) which has the ability to move, grow and interact with its neighbors. A non-

trivial problem that arises from this implementation is how to detect and correct for the

physical overlap that inevitably arises between these virtual growing, dividing objects, which

does not occur in real biological cell populations.

Previously, this issue has been dealt with by implementing a simple algorithm which compares

the position and radius of every cell with every other cell in the model. This algorithm is

effective, but computationally intensive (scaling as n-squared), so adds significant overhead to

what would otherwise be a lightweight simulation.

The objective of this project is to develop an alternative tree-based search approach to detect

contact or overlap between circles and compare the results and efficiency of this approach with

the results of the existing simple implementation for a set of test cases.