Re: [OT] Hints for an algorithm - avoiding O(n^2)

[jtg <jtg77@poczta.onet.pl>]

Dmitry A. Kazakov wrote:
> On Fri, 12 Mar 2004 12:55:19 +0000, Stuart Palin <stuart.palin@0.0>
> wrote:
> 
> 
>>Jean-Pierre Rosen wrote:
>>
>>>"Jano" <402450@cepsz.unizar.es> a �crit dans le message de 
>>
>>news:5d6fdb61.0403120115.7c102e3c@posting.google.com...
>>
>>>>The problem is a simple one: I'm planning to write a simulator of
>>>>sideral-like objects using the Newton laws (precision is not a top
>>>>priority). The obvious way is to compute the force interactions
>>>>between each pair of objects, sum them all, and iterate over... but
>>>>this is O(n^2). To be precise, there are n(n-1)/2 forces to be
>>>>computed if I'm right (n the number of objects).
>>>>
>>>
>>>If I remember my Newton laws correctly, you just need to compute the force
>>>between an object and the center of mass of all other objects.
>>
>>No!  It is quite a straight-forward proof to show that for a
>>point inside a uniformly dense sphere the mass at a greater
>>distance from the centre (than the point) has no net
>>gravitational effect on the point.
>>
>>Also a counter-example is very easy to construct.  Consider
>>two large equal masses separated by a large distance.  Their
>>centre of mass (which will be the sum of their masses) is at
>>the mid-point of the shortest line joining them.  Another
>>mass placed a little way from this mid-point will in fact
>>feel little gravitational effect because the masses are a
>>long way away.  However, a calculation based on the centre
>>of mass would suggest there is a very strong force acting!
> 
> 
> This is because the third object is within the sphere containing the
> first two. If I correctly remember, that is a consequence of the Gauss
> theorem. But if you arrange your objects in spheric clusters centered
> in their mass centers, so that the interesting object will be outside
> of any of them, then the result will hold. Whether that will be better
> than O(n**2)  is another question.

No! According to Newton laws the object can for instance orbit one of
the masses, but if you assume you can model the masses with one
mass between them, the object could instead only orbit the center
(which is actually empty) and could not orbit any of the masses!