×

Boundary labeling: Models and efficient algorithms for rectangular maps. (English) Zbl 1278.68308

Summary: We introduce boundary labeling, a new model for labeling point sites with large labels. According to the boundary-labeling model, labels are placed around an axis-parallel rectangle that contains the point sites, each label is connected to its corresponding site through a polygonal line called leader, and no two leaders intersect. Although boundary labeling is commonly used, e.g., for technical drawings and illustrations in medical atlases, this problem has not yet been studied in the literature. The problem is interesting in that it is a mixture of a label-placement and a graph-drawing problem.In this paper we investigate several variants of the boundary-labeling problem. We consider labels of identical or different size, straight-line or rectilinear leaders, fixed or sliding ports for attaching leaders to sites and attaching labels to one, two or all four sides of the bounding rectangle. For any variant of the boundary labeling model, we aim at highly esthetical placements of labels and leaders. We present simple and efficient algorithms that minimize the total leader length or, in the case of rectilinear leaders, the total number of bends.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
05C62 Graph representations (geometric and intersection representations, etc.)
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Agarwal, P. K.; Efrat, A.; Sharir, M., Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications, SIAM Journal on Computing, 29, 3, 912-953 (1999) · Zbl 0949.68179
[2] J. Ahn, H. Freeman, AUTONAP—an expert system for automatic map name placement, in: Proc. International Symposium on Spatial Data Handling (SDH’84), 1984, pp. 544-569; J. Ahn, H. Freeman, AUTONAP—an expert system for automatic map name placement, in: Proc. International Symposium on Spatial Data Handling (SDH’84), 1984, pp. 544-569
[3] Accessed 2005-11-08
[4] Binucci, C.; Didimo, W.; Liotta, G.; Nonato, M., Orthogonal drawings of graphs with vertex and edge labels, Computational Geometry: Theory and Applications, 32, 2, 71-114 (2005) · Zbl 1077.05504
[5] Booch, G.; Rumbaugh, J.; Jacobson, I., The Unified Modeling Language User Guide (1999), Addison-Wesley: Addison-Wesley Reading, MA
[6] Chazelle, B., The computational geometry impact task force report, (Chazelle, B.; Goodman, J. E.; Pollack, R., Advances in Discrete and Computational Geometry, vol. 223 (1999), American Mathematical Society: American Mathematical Society Providence, RI), 407-463
[7] H. Freeman, S. Marrinan, H. Chitalia, Automated labeling of soil survey maps, in: Proc. ASPRS-ACSM Annual Convention, Baltimore, vol. 1, 1996, pp. 51-59; H. Freeman, S. Marrinan, H. Chitalia, Automated labeling of soil survey maps, in: Proc. ASPRS-ACSM Annual Convention, Baltimore, vol. 1, 1996, pp. 51-59
[8] Fekete, J.-D.; Plaisant, C., Excentric labeling: Dynamic neighborhood labeling for data visualization, (Proc. Conference on Human Factors in Computer Systems (CHI’99) (1999), ACM: ACM New York), 512-519
[9] M. Formann, F. Wagner, A packing problem with applications to lettering of maps, in: Proc. 7th Annual ACM Symposium on Computational Geometry (SoCG’91), 1991, pp. 281-288; M. Formann, F. Wagner, A packing problem with applications to lettering of maps, in: Proc. 7th Annual ACM Symposium on Computational Geometry (SoCG’91), 1991, pp. 281-288
[10] Garrido, M.Á.; Iturriaga, C.; Márquez, A.; Ramon Portillo, J.; Reyes, P.; Wolff, A., Labeling subway lines, (Eades, P.; Takaoka, T., Proc. 12th Annual International Symposium on Algorithms and Computation (ISAAC’01). Proc. 12th Annual International Symposium on Algorithms and Computation (ISAAC’01), Lecture Notes in Computer Science, vol. 2223 (2001), Springer-Verlag: Springer-Verlag Berlin), 649-659 · Zbl 1077.68902
[11] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman: W.H. Freeman New York · Zbl 0411.68039
[12] Hirsch, S. A., An algorithm for automatic name placement around point data, The American Cartographer, 9, 1, 5-17 (1982)
[13] Hershberger, J.; Suri, S., Applications of a semi-dynamic convex hull algorithm, BIT, 32, 249-267 (1992) · Zbl 0761.68097
[14] Iturriaga, C.; Lubiw, A., Elastic labels around the perimeter of a map, Journal of Algorithms, 47, 1, 14-39 (2003) · Zbl 1045.68141
[15] C. Iturriaga, Map labeling problems, PhD thesis, University of Waterloo, 1999; C. Iturriaga, Map labeling problems, PhD thesis, University of Waterloo, 1999
[16] Klau, G. W.; Mutzel, P., Automatic layout and labelling of state diagrams, (Jäger, W.; Krebs, H.-J., Mathematics—Key Technology for the Future (2003), Springer-Verlag: Springer-Verlag Berlin), 584-608 · Zbl 1044.68131
[17] Kwon Kim, S.; Shin, C.-S.; Yang, T.-C., Labeling a rectilinear map with sliding labels, International Journal of Computational Geometry and Applications, 11, 2, 167-179 (2001) · Zbl 1074.68641
[18] Kakoulis, K. G.; Tollis, I. G., A unified approach to automatic label placement, International Journal of Computational Geometry and Applications, 13, 1, 23-59 (2003) · Zbl 1152.68669
[19] Lawler, E. L., Combinatorial Optimization: Networks and Matroids (1976), Holt, Rinehart & Winston: Holt, Rinehart & Winston New York · Zbl 0358.68059
[20] Mehlhorn, K., Data Structures and Algorithms 3: Multi-dimensional Searching and Computational Geometry, EATCS Monographs on Theoretical Computer Science, vol. 3 (1984), Springer-Verlag: Springer-Verlag Heidelberg · Zbl 0556.68003
[21] Morrison, J. L., Computer technology and cartographic change, (Taylor, D. R.F., The Computer in Contemporary Cartography (1980), Johns Hopkins University Press)
[22] Vaidya, P. M., Geometry helps in matching, SIAM Journal on Computing, 18, 1201-1225 (1989) · Zbl 0692.68042
[23] Accessed 2004-07-22
[24] Wolff, A.; Strijk, T., The map-labeling bibliography (1996)
[25] Zoraster, S., The solution of large 0-1 integer programming problems encountered in automated cartography, Operations Research, 38, 5, 752-759 (1990)
[26] Zoraster, S., Practical results using simulated annealing for point feature label placement, Cartography and GIS, 24, 4, 228-238 (1997)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.