Title

Achieving O(N) In Simulating The Billiards Problem In Discrete-Event Simulation

Abstract

This 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 occurring 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(N2) for a non-uniform distribution of N spatial objects.

Publication Date

1-1-1995

Publication Title

Winter Simulation Conference Proceedings

Number of Pages

751-756

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1145/224401.224724

Socpus ID

0029483982 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0029483982

This document is currently not available here.

Share

COinS