Shown above is an interactive simulation of a circle packing approximation algorithm.
Given a set of C of unit disks, find a subset C' of C such that all disks in C' are pairwise disjoint and |C'| is maximized. This is an NP-hard problem, so we instead provide a polynomial time approximation scheme that has accuracy ≥ 1 - ε where ε = O(1/k) and k is your chosen gridsize.
Our algorithm involves slicing the plane into grids of size k, and then solving the packing problem exactly within the grids.
Stitching together the results of each of the grids (and discarding any disks lying along the gridlines)
gives us a suitable approximation on a randomly selected choice of disks. Note that it is certainly possible to create frustrating
adversarial examples (i.e. placing all the disks along a set of grid lines which would lead to every disk being discarded) -
quite an unfortunate feature of this approach!
For more information, see here. The code is on github.