School of Computing

Detecting collisions in sets of moving particles: a survey and some experiments

Colin G. Johnson and Jacqueline Whalley

Technical Report 8-02, University of Kent, Computing Laboratory, June 2002.

Abstract

Detecting and responding to collisions between particles is an important requirement for building simulations in computational science. Due to the large number of potential collisions it is impractical to check all possibilities, so the development of algorithms which narrow down the number of possible searches to a small number is important. In this paper we review various algorithms for this task, and give results from a number of experiments which demonstrate the relative efficiency of these algorithms on a fundamental problem of detecting collisions between particles undergoing Brownian motion. The general slant of the paper is towards the development of algorithms for simulating microbiological systems.

Download publication 408 kbytes (PostScript)

Bibtex Record

@techreport{1500,
author = {Colin G. Johnson and Jacqueline Whalley},
title = {Detecting collisions in sets of moving particles: a survey and some experiments},
month = {June},
year = {2002},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/2002/1500},
    publication_type = {techreport},
    submission_id = {5868_1028824029},
    number = {8-02},
    institution = {University of Kent, Computing Laboratory},
}

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014