Aleksandar Doneva, b, Salvatore Torquatoa, b, c and Frank H. Stillingerc aProgram in Applied and Computational Mathematics, Princeton University, Princeton, NJ 08544, USA bPrinceton Institute for the Science and Technology of Materials, Princeton University, Princeton, NJ 08540, USA cDepartment of Chemistry, Princeton University, Princeton, NJ 08540, USA Revised 19 May 2004; accepted 9 August 2004. Available online 10 November 2004. Journal of Computational Physics Volume 202, Issue 2 , 20 January 2005, Pages 737-764 Abstract In this first part of a series of two papers, we present in considerable detail a collision-driven molecular dynamics algorithm for a system of non-spherical particles, within a parallelepiped simulation domain, under both periodic or hard-wall boundary conditions. The algorithm extends previous event-driven molecular dynamics algorithms for spheres, and is most efficient when applied to systems of particles with relatively small aspect ratios and with small variations in size. We present a novel partial-update near-neighbor list (NNL) algorithm that is superior to previous algorithms at high densities, without compromising the correctness of the algorithm. This efficiency of the algorithm is further increased for systems of very aspherical particles by using bounding sphere complexes (BSC). These techniques will be useful in any particle-based simulation, including Monte Carlo and time-driven molecular dynamics. Additionally, we allow for a non-vanishing rate of deformation of the boundary, which can be used to model macroscopic strain and also alleviate boundary effects for small systems. In the second part of this series of papers we specialize the algorithm to systems of ellipses and ellipsoids and present performance results for our implementation, demonstrating the practical utility of the algorithm.