Method of Means and Medians

The idea

Take the sinks where they actually are. Compute their center of mass (the mean); split the set into two equal halves by the median in x (or y, alternating per level); route from the center of mass to each half's center of mass; recurse within each half until single sinks remain. Every sink ends up reached through the same number of levels, and because each split halves the population geometrically, path lengths to the two sides of every branch are roughly equal, so skew is roughly controlled, for real, arbitrary sink distributions, which the H-tree could never handle.

Its place in history

This 1990 algorithm effectively founded clock routing as an algorithmic field: before it, balanced clocks meant hand-drawn symmetry; after it, clock trees were computed from the netlist's actual geometry. Its limits were understood immediately: it balances wire length statistically, not delay, ignores capacitive load differences, and guarantees nothing. Within two years both gaps were closed: exact zero-skew construction using the Elmore delay model (next page), then provably minimum-wirelength zero skew (the page after).

Where you meet it today

As the classic first lecture in clock synthesis, as a fast constructor inside larger systems (its top-down recursion still seeds some tools' initial topologies), and conceptually in every 'bipartition the sinks and recurse' clock heuristic since.