McGill University - School of Computer Science

Algorithms Seminar

Everybody is welcome.

DATE: Thursday, April 20th
TIME: 11:00 AM - 12:00 PM
PLACE: McConnell 320
TITLE: Labeling Maps with Elastic Labels
SPEAKER: Claudia Iturriaga, University of New Brunswick: Faculty of Computer Science

One of the most challenging tasks in cartography is the ``labeling'' of maps---attaching text to geographic features. Many of the issues become simpler when the features are points, for example cities on a large-scale map, because we expect the text to be placed horizontally and close to the associated point. We want labels that do not overlap and are large enough to be readable. Even simple formulations of this problem are NP-complete.

In this talk, I will present an alternative formulation to the map labeling problem. The use of ``elastic labels'', where each label is a rectangle with fixed area, but varying in height and width. Then, we define the ``elastic labeling problem'' as determining the choice of height and width of each label, and the corner of the label to place at the associated point, so that no two labels overlap. This problem is useful when the goal of placing a label at a given point is to associate some text, consisting of more than one word, with the point. In this case we can write the specified text inside the label using one, two, or more rows, as long as the label is placed at the specified point.

However, the elastic labeling problem is an NP-hard problem. Thus, we consider a problem with more constraints, yet of practical use. We require that the points lie on the boundary of a rectangular map. This ``rectangle perimeter labeling problem'' arises, for example, when the perimeter of the map is labeled with information about objects that lie beyond the boundary of the map, e.g. where the roads lead to. This problem is likely to be relevant in Geographical Information Systems (GIS) as maps are displayed dynamically on a computer screen using clipping, panning, and zooming.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at