HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE TCSC Research Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/691
Title: Labeling a rectilinear map with sliding labels
Authors: Kim, Sung Kwon
Shin, Chan-Su
Yang, Tae-Cheon
Keywords: Rectilinear map
Sliding rectangular labels
Map labeling
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 [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.
URI: http://hdl.handle.net/1783.1/691
Appears in Collections:CSE TCSC Research Reports

Files in This Item:

File Description SizeFormat
199906.pdf220KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.