HKUST Institutional Repository >
Computer Science and Engineering >
CSE TCSC Research Reports >
Please use this identifier to cite or link to this item:
|Title: ||Labeling a rectilinear map with sliding labels|
|Authors: ||Kim, Sung Kwon|
|Keywords: ||Rectilinear map|
Sliding rectangular labels
|Issue Date: ||2-Jul-1999 |
|Citation: ||International journal of computational geometry & applications, v.11, no.2, Apr. 2001, p. 167-179|
|Series/Report no.: ||HKUST Theoretical Computer Science Center Research Report ; HKUST-TCSC-99-06|
|Abstract: ||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  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 , 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 , our objective is to maximize the height of labels. Depending on the type of input segments, three different versions are possible.
A set of n non-intersecting horizontal segments is given and the segments are intersected by a common vertical line.
A set of n non-intersecting horizontal segments is given and there is no common vertical line that intersects all of the segments.
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.|
|Appears in Collections:||CSE TCSC Research Reports|
Files in This Item:
All items in this Repository are protected by copyright, with all rights reserved.