{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T03:41:27Z","timestamp":1777520487755,"version":"3.51.4"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T00:00:00Z","timestamp":1586217600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T00:00:00Z","timestamp":1586217600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider map labeling for the case that a map undergoes a sequence of operations such as rotation, zoom and translation over a specified time span. We unify and generalize several previous models for dynamic map labeling into one versatile and flexible model. In contrast to previous research, we completely abstract from the particular operations and express the labeling problem as a set of time intervals representing the labels\u2019 presences, activities and conflicts. One of the model\u2019s strength is manifested in its simplicity and broad range of applications. In particular, it supports label selection both for map features with fixed position as well as for moving entities (e.g., for tracking vehicles in logistics or air traffic control). We study the active range maximization problem in this model. We prove that the problem is -complete and [1]-hard, and present constant-factor approximation algorithms. In the restricted, yet practically relevant case that no more than <jats:italic>k<\/jats:italic> labels can be active at any time, we give polynomial-time algorithms as well as constant-factor approximation algorithms.<\/jats:p>","DOI":"10.1007\/s00453-020-00694-7","type":"journal-article","created":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T14:02:55Z","timestamp":1586268175000},"page":"2709-2736","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A Unified Model and Algorithms for Temporal Map Labeling"],"prefix":"10.1007","volume":"82","author":[{"given":"Andreas","family":"Gemsa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6638-7250","authenticated-orcid":false,"given":"Benjamin","family":"Niedermann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0454-3937","authenticated-orcid":false,"given":"Martin","family":"N\u00f6llenburg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,4,7]]},"reference":[{"issue":"5","key":"694_CR1","doi-asserted-by":"crossref","first-page":"773","DOI":"10.1109\/TVCG.2006.136","volume":"12","author":"K Been","year":"2006","unstructured":"Been, K., Daiches, E., Yap, C.: Dynamic map labeling. IEEE Trans. Vis. Comput. Graph. 12(5), 773\u2013780 (2006)","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"issue":"4","key":"694_CR2","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1142\/S0218195914600127","volume":"24","author":"K Buchin","year":"2014","unstructured":"Buchin, K., Gerrits, D.H.P.: Dynamic point labeling is strongly PSPACE-complete. Int. J. Comput. Geom. Appl. 24(4), 373\u2013395 (2014)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"694_CR3","doi-asserted-by":"crossref","unstructured":"Barth, L., Gemsa, A., Niedermann, B., N\u00f6llenburg, M.: Temporal map labeling: a new unified framework with experiments. In: Advances in Geographic Information Systems (ACM-GIS\u201916). ACM Press (2016)","DOI":"10.1145\/2996913.2996957"},{"issue":"3","key":"694_CR4","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1016\/j.comgeo.2009.03.006","volume":"43","author":"K Been","year":"2010","unstructured":"Been, K., N\u00f6llenburg, M., Poon, S.-H., Wolff, A.: Optimizing active ranges for consistent dynamic map labeling. Comput. Geom. Theory Appl. 43(3), 312\u2013328 (2010)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"3","key":"694_CR5","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0166-218X(95)80003-M","volume":"59","author":"MC Carlisle","year":"1995","unstructured":"Carlisle, M.C., Lloyd, E.L.: On the k-coloring of intervals. Discrete Appl. Math. 59(3), 225\u2013235 (1995)","journal-title":"Discrete Appl. Math."},{"key":"694_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/978-3-642-40450-4_32","volume-title":"Algorithms (ESA\u201913)","author":"M de Berg","year":"2013","unstructured":"de Berg, M., Gerrits, D.H.P.: Labeling moving points with a trade-off between label speed and label overlap. In: Bodlaender, H.L., Italiano, G.F. (eds.) Algorithms (ESA\u201913). Lecture Notes in Computer Science, vol. 8125, pp. 373\u2013384. Springer, Berlin (2013)"},{"issue":"3","key":"694_CR7","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","volume":"12","author":"RJ Fowler","year":"1981","unstructured":"Fowler, R.J., Paterson, M.S., Tanimoto, S.L.: Optimal packing and covering in the plane are NP-complete. Inf. Process. Lett. 12(3), 133\u2013137 (1981)","journal-title":"Inf. Process. Lett."},{"key":"694_CR8","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)"},{"key":"694_CR9","unstructured":"Gemsa, A., N\u00f6llenburg, M., Rutter, I.: Sliding labels for dynamic point labeling. In: Canadian Conference on Computational Geometry (CCCG\u201911), pp. 205\u2013210 (2011)"},{"issue":"1","key":"694_CR10","first-page":"308","volume":"7","author":"A Gemsa","year":"2016","unstructured":"Gemsa, A., N\u00f6llenburg, M., Rutter, I.: Consistent labeling of rotating maps. J. Comput. Geom. 7(1), 308\u2013331 (2016)","journal-title":"J. Comput. Geom."},{"issue":"1","key":"694_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2851493","volume":"21","author":"A Gemsa","year":"2016","unstructured":"Gemsa, A., N\u00f6llenburg, M., Rutter, I.: Evaluation of labeling strategies for rotating maps. J. Exp. Algorithmics 21(1), 1\u201321 (2016)","journal-title":"J. Exp. Algorithmics"},{"key":"694_CR12","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/B978-0-12-289260-8.50015-7","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Interval graphs, chapter 8. In: Golumbic, M.C. (ed.) Algorithmic Graph Theory and Perfect Graphs, pp. 171\u2013202. Academic Press, Cambridge (1980)"},{"issue":"5","key":"694_CR13","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0020-0190(92)90216-I","volume":"43","author":"JY Hsiao","year":"1992","unstructured":"Hsiao, J.Y., Tang, C.Y., Chang, R.S.: An efficient algorithm for finding a maximum weight 2-independent set on interval graphs. Inf. Process. Lett. 43(5), 229\u2013235 (1992)","journal-title":"Inf. Process. Lett."},{"key":"694_CR14","first-page":"170","volume-title":"Frontiers in Algorithmics (FAW\u201914). Lecture Notes in Computer Science","author":"C-S Liao","year":"2014","unstructured":"Liao, C.-S., Liang, C.-W., Poon, S.-H.: Approximation algorithms on consistent dynamic map labeling. In: Chen, J., Hopcroft, J.E., Wang, J. (eds.) Frontiers in Algorithmics (FAW\u201914). Lecture Notes in Computer Science, vol. 8497, pp. 170\u2013181. Springer, Cham (2014)"},{"issue":"6","key":"694_CR15","doi-asserted-by":"crossref","first-page":"1237","DOI":"10.1109\/TVCG.2008.152","volume":"14","author":"M Luboschik","year":"2008","unstructured":"Luboschik, M., Schumann, H., Cords, H.: Particle-based labeling: fast point-feature labeling without obscuring other visual features. IEEE Trans. Vis. Comput. Graph. 14(6), 1237\u20131244 (2008)","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"694_CR16","first-page":"448","volume-title":"Algorithms (ESA\u201905). Lecture Notes in Computer Science","author":"D Marx","year":"2005","unstructured":"Marx, D.: Efficient approximation schemes for geometric problems? In: Brodal, G.S., Leonardi, S. (eds.) Algorithms (ESA\u201905). Lecture Notes in Computer Science, vol. 3669, pp. 448\u2013459. Springer, Berlin (2005)"},{"key":"694_CR17","first-page":"1","volume-title":"Smart Graphics (SG\u201906). Lecture Notes in Computer Science","author":"S Maass","year":"2006","unstructured":"Maass, S., D\u00f6llner, J.: Efficient view management for dynamic annotation placement in virtual landscapes. In: Butz, A., Fisher, B., Kr\u00fcger, A., Olivier, P. (eds.) Smart Graphics (SG\u201906). Lecture Notes in Computer Science, vol. 4073, pp. 1\u201312. Springer, Berlin (2006)"},{"key":"694_CR18","doi-asserted-by":"crossref","unstructured":"Maass, S., D\u00f6llner, J.: Embedded labels for line features in interactive 3d virtual environments. In: Computer Graphics, Virtual Reality, Visualisation and Interaction (AFRIGRAPH\u201907), pp. 53\u201359. ACM Press (2007)","DOI":"10.1145\/1294685.1294695"},{"issue":"2","key":"694_CR19","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1037\/h0043158","volume":"63","author":"GA Miller","year":"1956","unstructured":"Miller, G.A.: The magical number seven, plus or minus two: some limits on our capacity for processing information. Psychol. Rev. 63(2), 81\u201397 (1956)","journal-title":"Psychol. Rev."},{"issue":"4","key":"694_CR20","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1057\/palgrave.ivs.9500163","volume":"6","author":"K Mote","year":"2007","unstructured":"Mote, K.: Fast point-feature label placement for dynamic visualizations. Inf. Vis. 6(4), 249\u2013260 (2007)","journal-title":"Inf. Vis."},{"key":"694_CR21","unstructured":"Petzold, I., Gr\u00f6ger, G., Pl\u00fcmer, L.: Fast screen map labeling\u2014data structures and algorithms. In: International Cartographic Conference (ICC\u201903), pp. 288\u2013298 (2003)"},{"key":"694_CR22","doi-asserted-by":"crossref","unstructured":"Sester, M., Brenner, C.: Continuous generalization for visualization on small mobile devices. In: Spatial Data Handling (SDH\u201904), pp. 355\u2013368. Springer, Berlin (2004)","DOI":"10.1007\/3-540-26772-7_27"},{"key":"694_CR23","first-page":"269","volume-title":"AGILE 2015. Lecture Notes in Geoinformation and Cartography","author":"N Schwartges","year":"2015","unstructured":"Schwartges, N., Morgan, B., Haunert, J.-H., Wolff, A.: Labeling streets along a route in interactive 3D maps using billboards. In: Bacao, F., Santos, M., Painho, M. (eds.) AGILE 2015. Lecture Notes in Geoinformation and Cartography, pp. 269\u2013287. Springer, Cham (2015)"},{"key":"694_CR24","doi-asserted-by":"crossref","unstructured":"Schwartges, N., Wolff, A., Haunert, J.-H.: Labeling streets in interactive maps using embedded labels. In: Advances in Geographic Information Systems (ACM-GIS\u201914), pp. 517\u2013520. ACM Press (2014)","DOI":"10.1145\/2666310.2666494"},{"key":"694_CR25","doi-asserted-by":"crossref","unstructured":"Vaaraniemi, M., Treib, M., Westermann, R.: Temporally coherent real-time labeling of dynamic scenes. In: Computing Geospatial Research Applications (COM.Geo\u201912), pp. 17:1\u201317:10. ACM Press (2012)","DOI":"10.1145\/2345316.2345337"},{"key":"694_CR26","unstructured":"Yokosuka, Y., Imai, K.: Polynomial time algorithms for label size maximization on rotating maps. In: Canadian Conference on Computational Geometry (CCCG\u201913), pp. 187\u2013192 (2013)"},{"key":"694_CR27","unstructured":"Zhang, X., Poon, S.-H., Li, M., Lee, V.: On maxmin active range problem for weighted consistent dynamic map labeling. In: GEOProcessing 2015, pp. 32\u201337. IARIA (2015)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00694-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00694-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00694-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,6]],"date-time":"2021-04-06T23:30:45Z","timestamp":1617751845000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00694-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,7]]},"references-count":27,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["694"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00694-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,7]]},"assertion":[{"value":"7 April 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}