I have a toy electrostatics simulation that consists of some number of 2D point particles that each have a real-valued "charge" $q_i$, which then exert forces on each other proportional to $q_i q_k r^{-2}$ ala Coulomb's Law. In principle, this sets up a vector field where the vector at each point is the sum of contributions proportional to $q_i r^{-2}$, but in practice I only need values at the locations of other particles. However, calculating this naively doesn't scale well, because it involves calculating $n^2$ force terms for $n$ particles, and I have been investigating how to do better.
One structure I have seen for dealing with this is a quadtree, which would represent my simulation space as a tree of disjoint regions, recursively dividing each region into quarters until they are small enough that each contains a small number of particles. (The empty regions can then be detected and discarded easily)
The reason I'm posting this as a mathematics rather than software question because my roadblock is determining what I want to be storing in the tree - I am confident that I can implement it once I understand that. I imagine that the solution has three parts:
- in the leaf nodes, each charge can be considered individually, and the force-field or potential can then be "summarized" somehow. I imagined that this summary might constitute coefficients of a multipole expansion or similar, but I don't know how to calculate MPEs in practice so that might be off-base.
- in the higher levels of the tree, I want to be looking at the four "summaries" of the level below and somehow combine them without referring to the individual points.
- at the root of the tree, the summary I end up with is a "good approximation" of the net field/potential of all of the charges, and I can then apply the forces given by this distribution to the particles.
When I say "good approximation", I don't expect that this method will produce exactly the answers I'd get from the naive method, but I do expect there will be some sort of parameter that would allow me to trade more computation time for better accuracy, e.g. more terms in series expansions.
Is there any way to break down interactions in this sort of spatially recursive way, either by using something like series expansions of the field within the sub-regions or with other methods?
