Published in Volume XXXI, Issue 2, 2021, pages 293-313, doi: 10.7561/SACS.2021.2.293

Authors: A.G. Rudi


For a map that can be rotated, we consider the following problem. There are a number of feature points on the map, each having a geometric object as a label. The goal is to find the largest subset of these labels such that when the map is rotated and the labels remain vertical, no two labels in the subset intersect. We show that, even if the labels are vertical bars of zero width, this problem remains NP-hard, and present a polynomial approximation scheme for solving it. We also introduce a new variant of the problem for vertical labels of zero width, in which any label that does not appear in the output must be coalesced with a label that does. Coalescing a subset of the labels means to choose a representative among them and set its label height to the sum of the individual label heights.

Full Text (PDF)


[1] P. K. Agarwal, M. J. van Kreveld, and S. Suri. Label placement by maximum independent set in rectangles. Computational Geometry, 11(3{4):209-218, 1998. doi:10.1016/S0925-7721(98)00028-5.

[2] K. Been, E. Daiches, and C.-K. Yap. Dynamic map labeling. IEEE Transactions on Visualization and Computer Graphics, 12(5):773-780, 2006. doi:10.1109/TVCG.2006.136.

[3] K. Been, M. Nollenburg, S.-H. Poon, and A. Wolff. Optimizing active ranges for consistent dynamic map labeling. Computational Geometry, 43(3):312-328, 2010. doi:10.1016/J.COMGEO.2009.03.006.

[4] R. G. Cano, C. C. de Souza, and P. J. de Rezende. Fast optimal labelings for rotating maps. In Sheung-Hung Poon, Md. Saidur Rahman, and Hsu-Chun Yen, editors, 11th International Conference and Workshops, WALCOM 2017, volume 10167 of Lecture Notes in Computer Science, pages 161-173. Springer, 2017. doi:10.1007/978-3-319-53925-6_13.

[5] T. M. Chan. Polynomial-time approximation schemes for packing and piercing fat objects. Journal of Algorithms, 46(2):178-189, 2003. doi:10.1016/S0196-6774(02)00294-8.

[6] T. M. Chan and S. Har-Peled. Approximation algorithms for maximum independent set of pseudo-disks. Discrete & Computational Geometry, 48(2):373-392, 2012. doi:10.1007/s00454-012-9417-5.

[7] T. Erlebach, T. Hagerup, K. Jansen, M. Minzlaff, and A. Wolff. Trimming of graphs, with application to point labeling. Theory of Computing Systems, 47(3):613-636, 2010. doi:10.1007/S00224-009-9184-8.

[8] T. Erlebach, K. Jansen, and E. Seidel. Polynomial-time approximation schemes for geometric intersection graphs. SIAM Journal on Computing, 34(6):1302-1323, 2005. doi:10.1137/S0097539702402676.

[9] M. Formann and F. Wagner. A packing problem with applications to lettering of maps. In Robert L. Scot Drysdale, editor, Seventh Annual Symposium on Computational Geometry, SoCG 1991, pages 281-288. ACM, 1991. doi:10.1145/109648.109680.

[10] R. J. Fowler, M. Paterson, and S. L. Tanimoto. Optimal packing and covering in the plane are NP-complete. Information Processing Letters, 12(3):133-137, 1981. doi:10.1016/0020-0190(81)90111-3.

[11] A. Gemsa, B. Niedermann, and M. Nollenburg. Trajectory-based dynamic map labeling. In Leizhen Cai, Siu-Wing Cheng, and Tak Wah Lam, editors, 24th International Symposium on Algorithms and Computation, ISAAC 2013, volume 8283 of Lecture Notes in Computer Science, pages 413-423. Springer, 2013. doi:10.1007/978-3-642-45030-3_39.

[12] A. Gemsa, M. Nollenburg, and I. Rutter. Consistent labeling of rotating maps. Computational Geometry, 7(1):308-331, 2011. doi:10.20382/jocg.v7i1a15.

[13] A. Gemsa, M. Nollenburg, and I. Rutter. Evaluation of labeling strategies for rotating maps. ACM Journal of Experimental Algorithmics, 21(1):1.4:1-1.4:21, 2016. doi:10.1145/2851493.

[14] D. S. Hochbaum and W. Maass. Approximation schemes for covering and packing problems in image processing and VLSI. Journal of the ACM, 32(1):130-136, 1985.  doi:10.1145/2455.214106.

[15] J. Hastad. Clique is hard to approximate within n^{1-epsilon}. Acta Mathematica, 182(1):105-142, 1999. doi:10.1007/BF02392825.

[16] W. D. Smith and N. C. Wormald. Geometric separator theorems and applications. In 39th Annual Symposium on Foundations of Computer Science, FOCS 1998, pages 232-243. IEEE Computer Society, 1998. doi:10.1109/SFCS.1998.743449.

[17] M. J. van Kreveld, T. Strijk, and A. Wolff. Point labeling with sliding labels. Computational Geometry, 13(1):21-47, 1999. doi:10.1016/S0925-7721(99)00005-X.

[18] Y. Yokosuka and K. Imai. Polynomial time algorithms for label size maximization on rotating maps. Journal of Information Processing, 25:572-579, 2017. doi:10.2197/ipsjjip.25.572.


  title={Maximizing the Number of Visible Labels on a Rotating Map},
  author={A.G. Rudi},
  journal={Scientific Annals of Computer Science},
  organization={Alexandru Ioan Cuza University, Ia\c si, Rom\^ania},
  publisher={Alexandru Ioan Cuza University Press, Ia\c si},