Please use this identifier to cite or link to this item:

Labeling a rectilinear map with sliding labels

Authors Kim, Sung Kwon
Shin, Chan-Su
Yang, Tae-Cheon
Issue Date 1999-07-02
Source International journal of computational geometry & applications , v.11, (2), 2001, April , p. 167-179
Summary Map labeling in geographic information systems has been considered to be important and well studied by the cartographic and computer science researchers [2, 5, 7]. In recent papers [3, 8, 10], the problem of labeling a rectilinear map was studied. A rectilinear map consists of a set of n mutually non-intersecting rectilinear (horizontal or vertical) line segments, and each segment is allowed to use a rectangular label of height B and length the same as the segment. A label can be placed at one of three positions, thus the problem is called the 3-position rectilinear segment labeling problem. As a generalization of the 3-position labeling problem, k-position problem, k >= 1, was also studied in several literatures. Van Kreveld, Strijk and Wolff [7] introduced the notion of sliding labels, where labels are not restricted to three (or any finite number of) predefined positions but can slide and be placed at any position as long as it intersects the object. In [7], they labeled p oints with sliding labels and introduced three different models of point labeling with sliding labels depending on the number of label sides allowed to touch points. Maximizing the number of points labeled was their objective, and they showed that the problem is NP-complete under the most general model of sliding labeling. A simple and efficient (1)/(2)-factor approximation algorithm was given. In this paper, we will consider labeling rectilinear maps with sliding rectangular labels, i.e, the infty-position rectilinear segment labeling problem will be considered. Unlike van Kreveld, Strijk and Wolff [7], our objective is to maximize the height of labels. Depending on the type of input segments, three different versions are possible. Problem 1D A set of n non-intersecting horizontal segments is given and the segments are intersected by a common vertical line. Problem 2D A set of n non-intersecting horizontal segments is given and there is no common vertical line that intersects all of the segments. Problem HV A set of n non-intersecting horizontal and vertical segments is given. In this paper efficient algorithms for the optimizations of these three problems will be given. For Problem 1D, a linear time algorithm is sufficient to solve it, after sorting the segments according to their y-coordinates. We next show that Problem 2D can be solved in a quadratic time. For Problem HV, we present a polynomial time "exact" algorithm and faster constant factor approximation algorithms.
Language English
Format Technical report
Files in this item:
File Description Size Format
199906.pdf 226276 B Adobe PDF