Abstract
We investigate a special class of map labeling problem. Let P = {p 1, p 2,..., p n} be a set of point sites distributed on a 2D map. A label associated with each point is a axis-parallel rectangle of a constant height but of variable width. Here height of a label indicates the font size and width indicates the number of characters in that label. For a point p i, its label contains the point p i at its top-left or bottom-left corner, and it does not obscure any other point in P. Width of the label for each point in P is known in advance. The objective is to label the maximum number of points on the map so that the placed labels are mutually nonoverlapping. We first consider a simple model for this problem. Here, for each point p i, the corner specification (i.e., whether the point p i would appear at the top-left or bottom-left corner of the label) is known. We formulate this problem as finding the maximum independent set of a chordal graph, and propose an O(nlogn) time algorithm for producing the optimal solution. If the corner specification of the points in P is not known, our algorithm is a 2-approximation algorithm. Next, we develop a good heuristic algorithm that is observed to produce optimal solutions for most of the randomly generated instances and for all the standard benchmarks available in [13].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
P. K. Agarwal, M. van Kreveld and S. Suri, Label placement by maximum independent set in rectangles, Computational Geometry: Theory and Applications, vol. 11, pp. 209–218, 1998.
B. Chazelle et at, Application challenges to computational geometry: CG impact task force report, http://www.cs.princeton.edu/~chazelle/taskforce/CGreport.ps, 1996.
S. Edmondson, J. Christensen, J. Marks, and S. Shieber, A general cartographic labeling algorithm, Cartographica, vol. 33, no. 4, pp. 13–23, 1997.
M. Formann and F. Wagner, A packing problem with applications to lettering of maps, Proc. 7th. Annual ACM Symp. on Computational Geometry, pp. 281–288, 1991.
M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, NY, 1980.
E. H. Isaaks and R. M. Srivastava, An Introduction to Applied Geostatistics, Oxford University Press, New York, 1989.
E. Imhof, Positioning names on maps, The American Cartographer, vol. 2, no. 2, pp. 128–144, 1975.
M. van Kreveld, T. Strijk and A. Wolff, Point labeling with sliding labels, Computational Geometry: Theory and Applications, vol. 13, pp. 21–47, 1999.
T. Strijk and M. van Kreveld, Labeling a rectilinear map more efficiently, Information Processing Letters, vol. 69, pp. 25–30, 1999.
T. Strijk and M. van Kreveld, Practical extension of point labeling in the slider model, 7th. Int. Symp. on Advances in Geographical Information Systems, (ACM-GIS’99), pp. 47–52, 1999.
C. K. Poon, B. Zhu and F. Chin, A polynomial time solution for labeling a rectilinear map, Proc. 13th. ACM Symp. on Computational Geometry, pp. 451–453, 1997.
F. P. Preparata and M. I. Shamos, Computational Geometry: An Introduction, Springer, Berlin, 1985.
A. Wolff, General Map Labeling Webpage, http://www.math-inf.uni-greifswald.de/map-labeling/general/.
F. Wagner, A. Wolff, A practical map labeling algorithm, Computational Geometry: Theory and Applications, vol. 7, pp. 387–404, 1997.
F. Wagner, A. Wolff, V. Kapoor and T. Strijk, Three rules suffice for good label placement, Algorithmica, vol. 30, pp. 334–349, 2001.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Roy, S., Goswami, P.P., Das, S., Nandy, S.C. (2002). Optimal Algorithm for a Special Point-Labeling Problem. In: Penttonen, M., Schmidt, E.M. (eds) Algorithm Theory — SWAT 2002. SWAT 2002. Lecture Notes in Computer Science, vol 2368. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45471-3_12
Download citation
DOI: https://doi.org/10.1007/3-540-45471-3_12
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43866-3
Online ISBN: 978-3-540-45471-7
eBook Packages: Springer Book Archive