Voronoi treemaps visualise hierarchical data by recursively partitioning convex polygons using weighted centroidal Voronoi diagrams. The polygon areas are proportional to the relative weights of their corresponding nodes.
The animation above shows the algorithm running one iteration at a time for each node of the tree.
For a static treemap, it’s more efficient to iterate until convergence for each node separately, rather than interleaving iterations.
This is because moving a parent Voronoi region can cause its child regions to be outside their parent, and this can happen repeatedly when interleaving. When this does happen, we simply reinsert such nodes at random locations within their parent.
This particular type of weighted Voronoi diagram is a power diagram.