Title: Fast Heuristic Optimization Methods for Point Label Placement Problem

Abstract: Point label placement problem is the problem of labeling points in graphical display systems such as mapbased ones in order to minimize conflicts of labels and thus to maximize legibility. Algorithmic complexity of the general problem is proven to be NP-hard. Addressing this problem is becoming more important in dynamic and real-time environments, where both display properties or point elements are subject to change, since those systems have potential use widely and in large scale. In this study, heuristic optimization methods are proposed to facilitate fast and goodquality labeling in such dynamic environments. The methods are two-phased and comprised of several combinations of greedy construction and local search methods. Performances of the methods are examined in terms of solution quality and run time. The eliminative, two-criteria method outperform other methods in this study and the methods proposed in the literature.

Keywords: Combinatorial optimization; heuristic algorithms; point labeling

Başlık: Nokta Etiketi Yerleştirme Problemi için Hızlı Sezgisel Eniyileme Yöntemleri

Özet: Nokta etiketi yerleştirme problemi harita tabanlı sistemler gibi grafiksel görüntüntüleme sistemlerinde noktasal ögelere ait etiketleri çakışmalarını asgariye indirecek şekilde yerleştirme ve böylece okunurluğu azamiye çıkarma problemidir. Genel olarak bu problemin NP-Zor algoritma karmaşıklık sınıfında olduğu ispatlanmıştır. Probleme çözüm üretmek, dinamik ve gerçek zamanlı sistemler için böyle sistemlerin yaygın ve geniş çaplı kullanılma potansiyelinden dolayı giderek önem kazanmaktadır. Bu çalışmada hem görüntüleme tercihlerinin değişebildiği, hem de noktasal ögelerin haraket edebildiği dinamik ortamlar için hızlı ve iyi kalitede etiket yerleştirmeyi sağlayabilecek sezgisel eniyileme yöntemleri önerilmektedir. Önerilen yöntemler iki aşamalı olup, hırslı inşa ve yerel aramadan oluşmaktadır. Yöntemlerin performansları çözüm kalitesi ve çalışma zamanı açısından incelenmiştir. Önerilen elemeli, iki kriterli yöntem hem bu çalışmadaki diğer yöntemlerden, hem de mevcut benzer çalışmadakinden daha iyi performans göstermektedir.

Anahtar kelimeler: Kombinatoryal eniyileme; sezgisel algoritmalar; nokta etiketleme

• Imhof E. Positioning names on maps. The American Cartographer 1975; 2(2):128-144.
• Christensen J, Marks J, Shieber S. An empirical study of algorithms for point-feature label placement. ACM Transactions on Graphics 1995; 14(3): 203–232.
• Marks J, Shieber S. The computational complexity of cartographic label placement. Technical Report TR-05-91, Harvard University, 1991.
• Zoraster S. The solution of large 0-1 integer programming problems encountered in automated cartography. Operations Research 1990; 38(5): 752-759.
• Mauri GR, Ribeiro GM, Lorena LAN. A new mathematical model and a Lagrangean decomposition for the point feature cartographic label placement problem. Computers and Operations Research 2010; 37: 2164–2172.
• Ribeiro GM, Constantino MF, Lorena LAN. Um estudo sobre desigualdades validas para o problema de maximizacao de rotulos livres. In XLI Brazilian Symposium on Operational Research, 2009, Porto Seguro, Brazil.
• Ribeiro GM, Lorena LAN. Lagrangean relaxation with clusters for point-feature cartographic label placement problems. Computers and Operations Research 2008; 35: 2129–2140.
• Strijk T, Verweij B, Aardal K. Algorithms for maximum independent set applied to map labelling, Department of Computer Science, Utrecht University, Technical Report UU-CS-2000-22, 2000.
• Verner OV, Wainwright RL, Schoenefeld DA. Placing text labels on maps and diagrams using genetic algorithms with masking. Journal on Computing 1997; 9(3): 266–275.
• Yamamoto M, Camara G, Lorena LAN. Tabu search heuristic for point-feature cartographic label placement. GeoInformatica 2002; 6(1): 77–90.
• Cravo GL, Ribeiro GM, Lorena LAN. A greedy randomized adaptive search procedure for the point-feature cartographic label placement. Computers and GeoSciences 2008; 34(4): 373–386.
• Rabello RL, Mauri GR, Ribeiro MR. A Clustering search metaheuristic for the point-feature cartographic label placement problem. European Journal of Operational Research 2014; 234: 802–808.
• Wagner F, Wolff A, Kapoor V, Strijk T. Three rules suffice for good label placement. Algorithmica 2001; 30: 334–346.
• Roy S, Bhattacharjee S, Das S, Nandy SC. A fast algorithm for point labeling problem. In 17th Canadian Conference on Computational Geometry (CCCG), 2005, Carleton University, Ottawa, Canada, pp. 155–158.
• Yamamoto M, Camara G, Lorena L. Fast point-feature label placement algorithm for real time screen maps. In GeoInfo 2005, 2005, Campos do Jordao, INPE, Sao Jose dos Campos, Brasil.
• Lorena LAN. Test problems. Retrieved from http://www.lac.inpe.br/~lorena/instancias.html