Point feature label placement (PFLP), a complex and usually NP-hard problem, is essential for automated cartography. Most approaches, other than arbitrary algorithms that might result in overlapping labels, are based on exhaustive search, greedy algorithms, forms of gradient descent where an initial configuration is improved iteratively, mathematical programming, or stochastic approaches. Gradient descent algorithms are shown to give good results, but can become trapped in local minima.
This valuable paper describes the AI stochastic approach of simulated annealing, which adds to gradient descent by allowing the algorithm to jump out of the local minima that can appear. In simulated annealing, the stochastic element is gradually reduced to zero over the iterations, and gradient descent remains. The results show that this approach is superior in terms of speed and the quality of the resulting map, especially in search spaces with complex terrains. The graphs comparing alternative PFLP algorithms are useful on their own.
The authors argue that their approach is among the easiest to implement in terms of lines of code. They maintain that it also separates the combinatorial-optimization and candidate-position-selection parts of the PFLP problem, which makes it easy to customize further.