Achieving O(N) in simulating the billiards problem in discrete-event simulation

Abstract

The paper identifies underlying issues associate with simulating those classes of problems which require both arbitrary spatial and temporal precision and which must deal the with the complexities of a multitude of asynchronous pair-wise interactions occuring among a dynamic non-uniform distribution of numerous spatial components. The principal issue of interest discussed focuses on a proposed simulation modeling methodology which dynamically sectors the trajectory space based on the number of spatial objects occupying a portion of the trajectory space (i.e. object space density). That is, the trajectory space is divided into sectors of various sizes such that each sector contains no more than some specified number of spatial components. The authors demonstrate that with such a dynamic sectoring methodology a theoretical reduction in the total number of pair-wise comparisons required during each time advancement can be achieved. Additionally, the theoretical computational complexity associated with identifying spatial conflicts will be better than O(N/sup 2/) for a non-uniform distribution of N spatial objects.