Labeling algorithm for points

Question

I need an algorithm to place horizontal text labels for multiple series of points on the screen (basically I need to show timestamps and other information for a history of moving objects on a map; in general there are multiple data points per object). The text labels should appear close to their points--above, below, or on the right side--but should not overlap other points or text labels.

Does anyone know an algorithm/heuristic for this?

• kmote: A related question is on SE:GIS: "Is there any simple Map Labeling Algorithm?"

Answer 1

It may come as a surprise to you that (if you want to ensure that none of the labels overlap) the problem you describe is NP-hard. On the other hand, many approximation algorithms have been devised that are perfectly useful in practice. It really depends on how difficult your specific constraints are. (Disclaimer: I wrote my Master's thesis on the subject -- available here -- so I'm probably exactly the wrong person to ask!) As always, Wikipedia and Google are good starting points. And if you're really a glutton, an exhausting (though not exhaustive) list of papers on the subject can be found here.

• Qwertie: Thanks. Since I couldn't find much info on this subject, I decided (before your reply) to implement a simple, if slightly braindead, overlap-avoidance strategy, coupled with a user interface so that the user can manually reposition labels. Figure 1 in your paper is impressive--I was lucky to have figured out where to click on CiteSeer to download it.
• kmote: I probably should have mentioned that my own approach was based on a fairly simple strategy as well (although it turned out to be surprisingly effective): Given a map of points to be labeled (each with given measure of "importance", defined arbitrarily), and a small number or "candidate" label locations surrounding each point, the algorithm simply starts with the "most important" points and calculates the "cost" of each candidate label location (where "cost" is basically the weighted sum of how many other points they would obscure.) ...
• kmote: [continued]... You simply pick the "least costly" label location, remove all the obscured points from your list, then move to the 2nd most "important" point and repeat the same procedure. All the most important points are guaranteed to get labeled, unless all their candidate locations are overlapped by more important labels. (I also threw in some tricky geometrics to make the overlapping cost calculation as efficient as possible. The resulting algorithm turned out to be pretty fast.) I'd love to hear what your efforts come up with.