I was in a location with no internet and no computing, so I spent an hour or so writing down what I think is the fast multipole method. It involves building an octtree, balanced in volume (not necessarily point content), and computing recursively the multipole amplitudes in all nodes (starting with the points in the leaves). Once that is done, at evaluation time, you do different things at different levels, depending on the radius out to which things are computed exactly. One thing I'm interested in is: Can you simplify that evaluation if you, say, build multiple trees?
Have you looked into VP trees? (Vantage point tree)
ReplyDelete