Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

This paper discusses a variety of ways to place diagrams like pie charts on maps, in particular, administrative subdivisions. The different ways come from different models of the placement problem: a diagram of one region should cover other regions, roads or boundaries as little as possible. In total we present six models for diagram placement. We outline three different algorithmic approaches and discuss the efficiency of each approach for the different models, and also for different types of diagrams (rectangular, circular, same or different sizes). We have implemented an algorithm for each model and show the resulting diagram placements on a number of maps. Our evaluation gives a first indication which model is best for aesthetically good diagram placement.

REFERENCES

• 1: Pankaj K. Agarwal , Alon Efrat , Micha Sharir, Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications, SIAM Journal on Computing, v.29 n.3, p.912-953, Dec. 1999 to Jan. 2000 [doi>10.1137/S0097539795295936]
• 2: Arikawa, M. and Kambayashi, Y. (1991). Dynamic name placement functions for interactive map systems. The Australian Computer Journal, 23(4):133--147.
• 3: Bentley, J. L. and Ottmann, T. A. (1979). Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput., C-28(9):643--647.
• 4: Bernard Chazelle , Herbert Edelsbrunner, An optimal algorithm for intersecting line segments in the plane, Journal of the ACM (JACM), v.39 n.1, p.1-54, Jan. 1992 [doi>10.1145/147508.147511]
• 5: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 6: Dent, B. D. (1999). Cartography: Thematic Map Design. McGraw-Hill, 5th edition.
• 7: Edmondson, S., Christensen, J., Marks, J., and Shieber, S. (1997). A general cartographic labeling algorithm. Cartographica, 33(4):13--23.
• 8: Glassman, B., editor (1996). The Macmillan Visual Almanac. Macmillan, New York.
• 9: Halperin, D. (2004). Arrangements. In Goodman, J. and O'Rourke, J., editors,Handbook of Discrete and Computational Geometry, chapter 24, pages 529--562. Chapman & Hall/CRC, Boca Raton, 2nd edition.
• 10: Harrie, L., Stigmar, H., Koivula, T., and Lehto, L. (2004). An algorithm for icon placement on a real-time map. In Proc. 11th Int. Symp. on Spatial Data Handling.
• 11: J. Hershberger, Finding the upper envelope of n line segments in O(n log n) time, Information Processing Letters, v.33 n.4, p.169-174, December 1989 [doi>10.1016/0020-0190(89)90136-1]
• 12: Mulmuley, K. (1993). Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ.
• 13: O'Rourke, J. (1995a). centroid.c. Available at ftp://cs.smith.edu/pub/code/centroid.c.
• 14: Joseph O'Rourke, Computational geometry in C, Cambridge University Press, New York, NY, 1994
• 15: I. Pinto , Herbert Freeman, The Feedback Approach to Cartographic Areal Text Placement, Proceedings of the 6th International Workshop on Advances in Structural and Syntactical Pattern Recognition, p.341-350, August 20-23, 1996
• 16: Robinson, A., Morrison, J., Muehrcke, P., Kimerling, A., and Guptill, S. (1995). Elements of Cartography. John Wiley & Sons, New York, 6th edition.
• 17: Tóth, G. F. (2004). Packing and covering. In Goodman, J. and O'Rourke, J., editors,Handbook of Discrete and Computational Geometry, chapter 2, pages 25--52. Chapman & Hall/CRC, Boca Raton, 2nd edition.
• 18: van Roessel, J. W. (1989). An algorithm for locating candidate labeling boxes within a polygon. The American Cartographer, 16(3):201--209.
• 19: Wolff, A. and Strijk, T. (1996). The Map-Labeling Bibliography. http://i11www.ira.uka.de/map-labeling/bibliography/.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Experimentation

Keywords:
cartographic visualization, placement algorithms