Close point of approch detection

Question

I have a large set of 3rd order polynomials in 3D.

in matrix form

[Pn](t) = [1,t,t^2,t^4]*[An] // [Pn] and [An] are matrices

each function has a weight Wn. I want to, for some n, m, T and t0 find the first t where t>t0 such that

Wn*Wm / |[Pn](t)-[Pm](t)|^2 > T

aside from a the O(n^2) "try everything" approach I'm not even sure where to start, For that matter, I'm not shure how to answer this even for the known n & m.

Any ideas

Edit:

• the set size is on the order of 10-1000
• the weight's are distributed ~ logarithmically (very few large, many small)
• this test would be in an inner loop of an n-body simulator so it would get run a lot
• versions that do well (amortized) at finding a new answer after on path is altered are a good thing.

Answer 1

Not knowing if this is solvable through analytic means, there are many approaches to searching a space and trying to find any t that meets that criteria.

Genetic algorithms, simulated annealing and other algorithms for optimization spring to mind.

Answer 2

OK to seed the pot:

• Using some form of "close pair finder" algorithm seed a heap with those pairs at t0 and other times.
• Pull the closest pair found
• if close enough and sooner than the best so far, keep
• find if they are closer or further apart
• split the difference between the current pair and the next one in on the "closer" side and add that the the heap.

Thoughts?

Answer 3

How large is N? Is an exhaustive search even possible?

I'd ask the question on the numpy or scipy discussion boards and brush up on your python skills. My bet is you could probably turn this into a minimisation problem and use fmin or BFGS or some other bounded quasi-Newton algorithm to find a reasonable minimum. Perhaps minimise the difference between t and T. Unless there is something weird in your matrices it looks like your search space may at least be continuous.

Since you mention closest point of approach in your title check this post out on the numpy board.