On 20/01/2023 16:52, Mark Waddingham via use-livecode wrote:
On 2023-01-20 13:05, Alex Tweedly via use-livecode wrote:
We need a better algorithm. If we use a "linear scan", we can change
it from essentially Order(N**2) to approx Order(N).
Slightly pedantic point (I appreciate that you did say 'approx')...
Sorting can not be done in any less time than O(N*log N) - so the
revised algorithm is O(N*log N) as you have to sort the input for it
to be able to scan linearly.
I figured someone would pick me up on that :-) It was a pretty big
'approx' :\)
The sorting step is indeed O(NlogN).
And the rest of it also worse than linear, but I don't have the math
knowledge to even begin to think about how much worse. Quick testing
says it's worse than O(NlogN), and in practice, it might even be as bad
as something like O(N * sqrt(N)), guessing about the number of points
within a (variable) sized window to the right of the current scan coord.
But in any "real app" usage that I can imagine, the 'clustering' effect
would seem to improve it over O(N*sqrt(N)); e.g. if the points tend to
cluster rather than be evenly randomly spread, then the number within
the scan window goes down on average. "real app" could be players in a
1st person player game, or vehicles on a road simulation, or (in 3d)
stars in the universe - in all cases causing the minDist to decrease
faster than when they are evenly spread.
Alex.
_______________________________________________
use-livecode mailing list
use-livecode@lists.runrev.com
Please visit this url to subscribe, unsubscribe and manage your subscription
preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
