Optimal Transport

Interpolation

Clustering

Simulation

Algorithms

I kind of feel like 3 skips over the important sub-point of "how do I determine an ideal position for a uniform distribution if my goal is to determine a uniform distribution for these points?"

Job van der Zwan

I wonder how to adapt this technique to make an equivalent "clustered force layout" for a huge set of points... could it work?

Andres Snitcofsky

I guess so—it's a pretty simple technique after all. If you want to create a notebook with data and share it with me, we could explore this together?

I need to fix up that radix sort so we can have that sweet, sweet O(kn) (where k = number of passes) complexity

Would be neat! In the iterative OT, the indices are often close to a correct order (forward or reverse). I don't know what the implications are on the sort algo, though. If it's important, we could use a different array for "vertical" and for "horizontal" sorts, and limit the angles to "top to bottom" and "left to right". (Note that in the example below, the bottleneck is drawing the dots.)

Actually I got some old code for a sort of "sprite blitter" somewhere that might help there (basically, it's worth it if the number of path calls becomes so large that replacing them with writing an NxN sprite into an RGBA array + a single call to putImageData is faster. Four, five years ago when I wrote it it took a surprisingly low number of circles for that to work out, but I don't know how browser optimizations have changed since then)

And of course WebGL would beat both options

As for the radix sort, it can be made to be faster for near-sorted and sorted arrays. So you need both an ascending and descending sort? Because my current version only has ascending sort but adding that is trivial.

ascending is enough, but if we want to keep near-sorted arrays we'll have to control which array we use depending on the angle