score:5

Accepted answer

See comments to the main question for how this developed...

Mike Bostock has created a couple of different visualizations of Mitchell's best-candidate sampling algorithm:

The original purpose of Mitchell's algorithm is to sample a range of values, in a way that doesn't create repetitive patterns, but also isn't prone to creating clusters and gaps like a true random sample.

Bostock's demonstrations combine the sampling algorithm with the d3 quadtree data structure, which sorts data points into a tree structure that is divided into just as many branches as are needed to put each data point into its own node. With the quadtree, Bostock can quickly tell how much space there is around each new point added to the graph, and therefore how large a circle can fit in that space. The program starts by drawing circles of a chosen maximum radius, and keeps going until it repeatedly fails to find enough room to draw circles of the minimum radius.

Bostock's examples used a rectangular space in which to draw the circles, but as Vivid D demonstrated, it can be adapted to other shapes.


Related Query

More Query from same tag