Algorithms Seminar

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.