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

[Dmitry A. Kazakov <mailbox@dmitry-kazakov.de>]

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 help to the OP - they might be better off posting in an
>astronomical group as this is more likely to be where people
>with knowledge of any special algorithms might hang out.

--
Regards,
Dmitry Kazakov
www.dmitry-kazakov.de