A POPMUSIC heuristic for the Point Feature Label Placement Problem
Adriana C. F. Alvim, Éric D. Taillard, Route de Cheseaux · 2007
This work, outlined in Alvim and Taillard [1], address the point feature label placement problem (PFLP) which is the problem of placing text labels adjacent to point features on a map so as to maximize legibility. We consider a set of n points, each one with p candidate label positions. A solution S is a list of n labels. For any S, we denote by f(S) the function that counts the number of point features labeled with one or more overlaps (in other words, the number of labels with conflicts) and by c(S) the function that counts the number of overlaps. The goal is to minimize c(S). Cartographic preferences also can be taken into account. For p ≥ 4, the PFLP is NP-hard [2]. With increasing use of electronic maps, fast and good labeling algorithms must be designed. The POPMUSIC approach proposed in [1] is analyzed under a practical complexity point of view. Computational time measures confirm that our POPMUSIC approach typically runs in O(n · p log(n · p)) while producing solution of higher quality than any other heuristic approach previously proposed.