ChatGPT examples

[Geoff Canyon]

I'm sure someone has done the work to create a more efficient algorithm for
this. Off the top of my head if I were trying to  I'd probably do something
like:

1. Grab two points at random (in case the points are pre-sorted in some
way) and get the distance.
2. Assume that's a reasonable average distance between points.
3. Define that as the number to beat, and define a grid based on it.
4. Go through all the points, tossing them into buckets based on the grid.
I'd define the buckets as fully overlapping to avoid missing close pairs.
5. The size of the grid buckets is critical: too big and you do too much
work. Too small and you end up with all singletons in the buckets. This
would require some experimentation and thought.
6. Go through the buckets only comparing the points within them.

On Fri, Jan 20, 2023 at 10:14 AM Alex Tweedly via use-livecode <
use-livecode at lists.runrev.com> wrote:

>
> 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 at lists.runrev.com
> Please visit this url to subscribe, unsubscribe and manage your
> subscription preferences:
> http://lists.runrev.com/mailman/listinfo/use-livecode
>