{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T21:07:14Z","timestamp":1766178434811,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2015,7,27]],"date-time":"2015-07-27T00:00:00Z","timestamp":1437955200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"KIT","award":["YIG 10-209"],"award-info":[{"award-number":["YIG 10-209"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2015,8,13]]},"abstract":"<jats:p>Boundary labeling deals with placing annotations for objects in an image on the boundary of that image. This problem occurs frequently in situations in which placing labels directly in the image is impossible or produces too much visual clutter. Examples are annotating maps, photos, or technical\/medical illustrations. Previous algorithmic results for boundary labeling consider a single layer of labels along some or all sides of a rectangular image. If, however, the number of labels is large or the labels are too long, multiple layers of labels are needed.<\/jats:p>\n          <jats:p>\n            In this article, we study boundary labeling for panorama images, where\n            <jats:italic>n<\/jats:italic>\n            points in a rectangle\n            <jats:italic>R<\/jats:italic>\n            are to be annotated by disjoint unit-height rectangular labels placed above\n            <jats:italic>R<\/jats:italic>\n            in\n            <jats:italic>K<\/jats:italic>\n            different rows (or layers). Each point is connected to its label by a vertical leader that does not intersect any other label. We present polynomial time algorithms based on dynamic programming that either minimize the number of rows to place all\n            <jats:italic>n<\/jats:italic>\n            labels or maximize the number (or total weight) of labels that can be placed in\n            <jats:italic>K<\/jats:italic>\n            rows for a given integer\n            <jats:italic>K<\/jats:italic>\n            . For weighted labels, the problem is shown to be (weakly) NP-hard; in this case, we give a pseudo-polynomial algorithm to maximize the weight of the selected labels. We have implemented our algorithms; the experimental results show that solutions for realistically sized instances are computed instantaneously. We have also investigated two-sided panorama labeling, for which the labels may be placed above or below the panorama image. In this model, all of the aforementioned problems are NP-hard. For solving them, we propose mixed-integer linear program formulations.\n          <\/jats:p>","DOI":"10.1145\/2794299","type":"journal-article","created":{"date-parts":[[2016,5,21]],"date-time":"2016-05-21T22:27:38Z","timestamp":1463869658000},"page":"1-30","source":"Crossref","is-referenced-by-count":9,"title":["Multirow Boundary-Labeling Algorithms for Panorama Images"],"prefix":"10.1145","volume":"1","author":[{"given":"Andreas","family":"Gemsa","sequence":"first","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}]},{"given":"Jan-Henrik","family":"Haunert","sequence":"additional","affiliation":[{"name":"University of Osnabr\u00fcck, Osnabr\u00fcck, Germany"}]},{"given":"Martin","family":"N\u00f6llenburg","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}]}],"member":"320","published-online":{"date-parts":[[2015,7,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90037-0"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 21st International Symposium on Graph Drawing (GD\u201913)","volume":"8242","author":"Bekos Michael","year":"2014","unstructured":"Michael Bekos , Sabine Cornelsen , Martin Fink , Seok-Hee Hong , Michael Kaufmann , Martin N\u00f6llenburg , Ignaz Rutter , and Antonios Symvonis . 2014 . Many-to-one boundary labeling with backbones . In Proceedings of the 21st International Symposium on Graph Drawing (GD\u201913) (Lecture Notes in Computer Science) , Vol. 8242 . Springer, 244--255. Michael Bekos, Sabine Cornelsen, Martin Fink, Seok-Hee Hong, Michael Kaufmann, Martin N\u00f6llenburg, Ignaz Rutter, and Antonios Symvonis. 2014. Many-to-one boundary labeling with backbones. In Proceedings of the 21st International Symposium on Graph Drawing (GD\u201913) (Lecture Notes in Computer Science), Vol. 8242. Springer, 244--255."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9283-6"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/11944836_10"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxp087"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00170"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2006.05.003"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00189"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 25th Urban Data Management Symposium (UDMS\u201906)","author":"Brenner Claus","year":"2006","unstructured":"Claus Brenner , Volker Paelke , Jan-Henrik Haunert , and Nora Ripperda . 2006 . The geoscope -- a mixed-reality system for planning and public participation . In Proceedings of the 25th Urban Data Management Symposium (UDMS\u201906) . Claus Brenner, Volker Paelke, Jan-Henrik Haunert, and Nora Ripperda. 2006. The geoscope -- a mixed-reality system for planning and public participation. In Proceedings of the 25th Urban Data Management Symposium (UDMS\u201906)."},{"volume-title":"Applied integer programming: modeling and solution","author":"Chen Der-San","key":"e_1_2_1_10_1","unstructured":"Der-San Chen , Robert G. Batson , and Yu Dang . 2011. Applied integer programming: modeling and solution . Wiley , Hoboken, NJ . Der-San Chen, Robert G. Batson, and Yu Dang. 2011. Applied integer programming: modeling and solution. Wiley, Hoboken, NJ."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2012.193"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/109648.109680"},{"key":"e_1_2_1_13_1","unstructured":"M. R. Garey and D. S. Johnson. 1990. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co.   M. R. Garey and D. S. Johnson. 1990. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45678-3_55"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2093973.2094012"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/APVIS.2007.329277"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11536482_10"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-04657-0_7"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03456-5_20"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40104-6_40"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACIFICVIS.2010.5429592"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1869790.1869834"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1063-0"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(99)00005-X"},{"key":"e_1_2_1_25_1","volume-title":"Retrieved","author":"Wolff Alexander","year":"1996","unstructured":"Alexander Wolff and Tycho Strijk . 1996 . The Map-Labeling Bibliography . Retrieved June 26, 2015 from http:\/\/i11www.iti.kit.edu\/map-labeling\/bibliography. Alexander Wolff and Tycho Strijk. 1996. The Map-Labeling Bibliography. Retrieved June 26, 2015 from http:\/\/i11www.iti.kit.edu\/map-labeling\/bibliography."}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2794299","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2794299","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:04:27Z","timestamp":1750273467000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2794299"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,27]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,8,13]]}},"alternative-id":["10.1145\/2794299"],"URL":"https:\/\/doi.org\/10.1145\/2794299","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"type":"print","value":"2374-0353"},{"type":"electronic","value":"2374-0361"}],"subject":[],"published":{"date-parts":[[2015,7,27]]}}}