Overview
A Verlet neighbor list stores particles within a cutoff radius plus a buffer distance. The simulation reuses that list until particles have moved far enough that the list must be rebuilt.
CoreSource checked
Verlet Neighbor List
Caches nearby particle pairs so neighbor searches can be reused across several simulation steps.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Simulation
- Difficulty
- Intermediate
- Family
- Particle Simulation
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 5
- Code example
- Ready
- Visualization
- Ready
Core Concepts
neighbor searchparticle simulationspatial approximationsimulation
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(1)
Average
O(n)
Worst
O(n)
Space
O(1)
When to Use
- Use when particles move gradually and short-range interactions dominate.
- Use when rebuilding a spatial index every timestep is more expensive than maintaining a buffered list.
When Not to Use
- Avoid when particles can move farther than the buffer between rebuild checks.
- Avoid when all particles interact globally and no cutoff is meaningful.
What It Does
- Builds candidate neighbor pairs with a cutoff buffer
- Reuses the list across timesteps
- Rebuilds when particle movement exceeds the buffer allowance
Use Cases
- Molecular dynamics neighbor searches
- Particle simulations with short-range forces
- Reducing repeated pair checks between rebuilds
Inputs
- Particle coordinates x_i, interaction cutoff radius r_c, and skin buffer r_s
Outputs
- Per-particle candidate neighbor lists within cutoff r_c + r_s
- Displacement trigger flag for list rebuilds
Pseudocode
- 1.Build neighbor pairs within cutoff plus buffer distance
- 2.For each timestep, compute interactions only for listed pairs within cutoff
- 3.Track each particle's displacement since the last rebuild
- 4.If maximum displacement exceeds the rebuild threshold, rebuild the list
- 5.Advance the simulation state
Canonical Example
- Input
- cutoff 1.0, buffer 0.2, particles A and B initially 1.1 apart
- Output
- A-B is kept as a candidate pair until the next rebuild decision
- Explanation
- The pair is outside the force cutoff but inside the buffered neighbor radius.
Implementation Notes
- Track maximum particle displacement since the last rebuild.
- Rebuild when displacement exceeds half the buffer distance.
- Combine the list with cell lists or spatial hashing for large systems.
Common Pitfalls
- A buffer that is too small can miss interactions before the next rebuild.
- A buffer that is too large creates too many candidate pairs.
- Periodic boundaries must be handled consistently during build and query.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow caching nearby particles within a buffer distance between rebuilds on a small neighbor search example.
Step 1 of 5: Build neighbor pairs within cutoff plus buffer distance
simulation-mechanismNotes
The buffer distance is a performance and correctness parameter: too small risks stale lists, too large wastes pair checks.
Sources (1)
What each reference supports for this entry.
Computer Animation: Algorithms and Techniques
BookSimulation reference covering Verlet Neighbor List integration, particle update, constraint, or animation workflow.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
AlternativesFast Multipole Method
Simulation · Specialized
Fast Multipole Method approximates far-field interactions, while Verlet neighbor lists reduce short-range pair checks.
Compare with thisOften paired withSpatial Hash
Data Structures · Core
Spatial hashing is commonly used to build neighbor lists efficiently.
Compare with thisOften paired withSweep and Prune
Simulation · Core
Both reduce broad neighbor or collision checks before expensive narrow computations.
Compare with thisRelationships
View full relationship pageOften paired withSweep and Prune
Both reduce broad neighbor or collision checks before expensive narrow computations.
Conceptual neighborN-Body Simulation
Neighbor lists help particle simulations avoid checking every pair when interactions are short-range.
Often paired withSpatial Hash
Spatial hashing is commonly used to build neighbor lists efficiently.
Related Algorithms
Tags
Simulation