Abstract
A set of points shown on the map usually represents special sites like cities or towns in a country. If the map in the interactive geographical information system (GIS) is browsed by users on the computer screen or on the web, the points and their labels can be viewed in a query window at different resolutions by zooming in or out according to the users’ requirements. How can we make use of the information obtained from different resolutions to avoid doing the whole labeling from scratch every time the zooming factor changes? We investigate this important issue in the interactive GIS system. In this paper, we build low-height hierarchies for one and two dimensions so that optimal and approximating solutions for adaptive zooming queries can be answered efficiently. To the best of our knowledge, no previous results have been known on this issue with theoretical guarantees.
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
Agarwal, P.K., van Kreveld, M., Suri, S.: Label placement by maximum independent set in rectangles. Computational Geometry: Theory and Applications 11, 209–218 (1998)
Arikawa, M., Kambayashi, Y., Kai, H.: Adaptive geographic information media using display agents for name placement. Trans. Journal of the Geographic Information Systems Association (1997) (in Japanese)
Arikawa, M., Kawakita, H., Kambayashi, Y.: An environment for generating interactive maps with compromises between users’ requirements and limitations of display screens. Trans. Journal of the Geographic Information Systems Association 2 (March 1993) (in Japanese)
Chan, T.: A Note on Maximum Independent Sets in Rectangle Intersection Graphs. Information Processing Letters 89(1), 19–23 (2004)
Chazelle, B., 36 co-authors: The computational geometry impact task force report. In: Chazelle, B., Goodman, J.E., Pollack, R. (eds.) Advances in Discrete and Computational Geometry, vol. 223, pp. 407–463. American Mathematical Society, Providence (1999)
de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications. Springer, Heidelberg (1997)
Formann, M., Wagner, F.: A packing problem with applications to lettering of maps. In: Proc. 7th Annu. ACM Sympos. Comput. Geom., pp. 281–288 (1991)
Knuth, D.E., Raghunathan, A.: The problem of compatible representatives. SIAM J. Discrete Math. 5(3), 422–427 (1992)
MapFactory, http://home.coqui.net/rjvaasjo/index.htm
Marks, J., Shieber, S.: The computational complexity of cartographic label placement. Technical report, Harvard CS (1991)
Petzold, I., Plumer, L., Heber, M.: Label placement for dynamically generated screen maps. In: Proceedings of the Ottawa ICA, pp. 893–903 (1999)
Roy, S., Goswami, P.P., Das, S., Nandy, S.C.: Optimal Algorithm for a Special Point-Labeling Problem. In: Penttonen, M., Schmidt, E.M. (eds.) SWAT 2002. LNCS, vol. 2368, pp. 110–120. Springer, Heidelberg (2002)
Strijk, T., Wolff, A.: http://www.math-inf.uni-greifswald.de/map-labeling/bibliography/
van Kreveld, M.: http://www.cs.uu.nl/centers/give/geometry/autocarto/index.html
van Kreveld, M., Strijk, T., Wolff, A.: Point labeling with sliding labels. Computational Geometry: Theory and Applications 13, 21–47 (1999)
van Kreveld, M., van Oostrum, R., Snoeyink, J.: Efficient settlement selection for interactive display. In: Proc. Auto-Carto 13: ACSM/ASPRS Annual Convention Technical Papers, pp. 287–296 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Poon, SH., Shin, CS. (2005). Adaptive Zooming in Point Set Labeling. In: Liśkiewicz, M., Reischuk, R. (eds) Fundamentals of Computation Theory. FCT 2005. Lecture Notes in Computer Science, vol 3623. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11537311_21
Download citation
DOI: https://doi.org/10.1007/11537311_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28193-1
Online ISBN: 978-3-540-31873-6
eBook Packages: Computer ScienceComputer Science (R0)