Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/691
Labeling a rectilinear map with sliding labels
Authors  Kim, Sung Kwon
Shin, ChanSu Yang, TaeCheon 


Issue Date  19990702  
Source  International journal of computational geometry & applications , v.11, (2), 2001, April , p. 167179  
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 nonintersecting 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 3position rectilinear segment labeling problem. As a generalization of the 3position labeling problem, kposition 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 NPcomplete 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 inftyposition 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 nonintersecting horizontal segments is given and the segments are intersected by a common vertical line. Problem 2D A set of n nonintersecting horizontal segments is given and there is no common vertical line that intersects all of the segments. Problem HV A set of n nonintersecting 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 ycoordinates. 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.  
Subjects  
Language  English 

Format  Technical report  
Access 
Files in this item:
