alex at tweedly.net
Fri Jan 20 13:14:10 EST 2023
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
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.
More information about the use-livecode