Editing Automatic label placement (section)

==Divide-and-conquer algorithms==
One simple optimization that is important on real maps is dividing a set of labels into smaller sets that can be solved independently. Two labels are ''rivals'' if they can overlap in one of the possible placements. [[transitive relation|Transitive]] closure of this relation divides the set of labels into possibly much smaller sets. On uniformly and densely labelled maps, usually the single set will contain the majority of labels, and on maps for which the labelling is not uniform it may bring very big performance benefits. For example, when labelling a map of the world, [[United States|America]] is labelled independently from [[Eurasia]] etc.