Deferred-Merge Embedding

The idea

Tsay's method balances each merge exactly but places each merge point greedily, freezing geometry too early. Deferred-Merge Embedding (DME) observes that for any two subtrees, the set of points where a zero-skew merge is possible at minimal wire cost is not one point but a segment: in Manhattan geometry, loci of equal distance are diagonal line segments (tilted 45 degrees), and intersecting the delay-balance condition with them yields a merging segment. So run two passes. Bottom-up: for each pairing, compute and store the merging segment, built from the children's segments, without choosing any point. Top-down: place the root wherever its segment allows (or at the clock source), then walk down choosing for each child the point of its merging segment nearest the parent's chosen point. Every choice is then provably wire-minimal for the given topology, and skew is exactly zero in the Elmore model.

Topology choice (which sinks pair with which) remains a degree of freedom; the Greedy-DME / clustering variants (Edahiro's, notably) choose pairings by nearest-neighbor clustering at each level and made the pipeline fast and practical.

Why it is the canonical algorithm

It is an exactly optimal (for wire, given topology and model) polynomial-time construction for a problem industry runs daily. Extensions handle bounded skew (segments become regions), buffered merges, obstacle avoidance, and slew constraints.

Where you meet it today

Directly inside modern clock synthesizers: OpenROAD's TritonCTS builds its trees on DME-style construction with clustering and buffering layered on. When this site's clock-tree problem talks about balanced merges, this is the method behind the words.