An Algorithm for the Map Labeling Problem with Two Kinds of Priorities

Authors: Noboru Abe, Yoshinori Amai, Toshinori Nakatake, Sumio Masuda, Kazuaki Yamaguchi

Abstract:

We consider the problem of placing labels of the points on a plane. For each point, its position, the size of its label and a priority are given. Moreover, several candidates of its label positions are prespecified, and each of such label positions is assigned a priority. The objective of our problem is to maximize the total sum of priorities of placed labels and their points. By refining a labeling algorithm that can use these priorities, we propose a new heuristic algorithm which is more suitable for treating the assigned priorities.

Keywords: Map labeling, greedy algorithm, heuristic algorithm, priority.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1337197

References:

[1] A. Wolff, The Map-Labeling Bibliography, http://i11www.ira.uka.de/map-labeling/bibliography/.
[2] F. Wagner and A. Wolff, "A combinatorial framework for map labeling problem,” Proc. 6th Int’l Symp. Graph Drawing (GD’98), Lecture Notes in Computer Sciences, Volume.1547, pp.316-331, Springer, Berlin, 1998.
[3] F. Wagner, A. Wolff, V. Kapoor and T. Strijk, "Three rules suffice for good label placement,” Algorithmica, Volume 30, No.2, pp.334-349, 2001.
[4] K. Funakawa, N. Abe, K. Yamaguchi and S. Masuda, "Algorithms for the map labeling problem with priorities” (in Japanese), IEICE Trans. Fundamentals, Volume J88-A, No.5, pp.677-681, 2005.
[5] N. Abe, M. Kusaki, S. Masuda and K. Yamaguchi, "An algorithm for placing labels of the points and chains on a map,” International Journal of Information Science and Computer Mathematics, Volume 4, Issue 2, pp.79-99, 2011.