{"id":182995,"updated":"2025-01-20T03:50:21.239012+00:00","links":{},"created":"2025-01-19T00:50:33.307852+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00182995","sets":["581:8997:9006"]},"path":["9006"],"owner":"11","recid":"182995","title":["Polynomial Time Algorithms for Label Size Maximization on Rotating Maps"],"pubdate":{"attribute_name":"公開日","attribute_value":"2017-08-15"},"_buckets":{"deposit":"0486dfc9-192a-47e8-b2ad-d1c39f466533"},"_deposit":{"id":"182995","pid":{"type":"depid","value":"182995","revision_id":0},"owners":[11],"status":"published","created_by":11},"item_title":"Polynomial Time Algorithms for Label Size Maximization on Rotating Maps","author_link":["400109","400111","400112","400110"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Polynomial Time Algorithms for Label Size Maximization on Rotating Maps"},{"subitem_title":"Polynomial Time Algorithms for Label Size Maximization on Rotating Maps","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"[特集：離散と計算の幾何・グラフ・ゲーム] map labeling, label size maximization, dynamic maps, rotating maps","subitem_subject_scheme":"Other"}]},"item_type_id":"2","publish_date":"2017-08-15","item_2_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"Information and System Engineering Course, Graduate School of Science and Engineering, Chuo University"},{"subitem_text_value":"Department of Information and System Engineering, Faculty of Science and Engineering, Chuo University"}]},"item_2_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Information and System Engineering Course, Graduate School of Science and Engineering, Chuo University","subitem_text_language":"en"},{"subitem_text_value":"Department of Information and System Engineering, Faculty of Science and Engineering, Chuo University","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/182995/files/IPSJ-JNL5808009.pdf","label":"IPSJ-JNL5808009.pdf"},"date":[{"dateType":"Available","dateValue":"2019-08-15"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-JNL5808009.pdf","filesize":[{"value":"456.5 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"0","billingrole":"5"},{"tax":["include_tax"],"price":"0","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"8"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"aaef5a6a-7e67-4e94-b9de-935f8b134fc4","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2017 by the Information Processing Society of Japan"}]},"item_2_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Yusuke, Yokosuka"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Keiko, Imai"}],"nameIdentifiers":[{}]}]},"item_2_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Yusuke, Yokosuka","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Keiko, Imai","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_2_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN00116647","subitem_source_identifier_type":"NCID"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_6501","resourcetype":"journal article"}]},"item_2_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"1882-7764","subitem_source_identifier_type":"ISSN"}]},"item_2_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"Map labeling is the problem of placing labels at corresponding graphical features on a map. There are two main optimization problems: the label number maximization problem and the label size maximization problem. In general, both problems are NP-hard for static maps. Recently, the widespread use of several applications, such as personal mapping systems, has increased the importance of dynamic maps and the label number maximization problem for dynamic cases has been studied. In this paper, we consider the label size maximization problem for points on rotating maps. Our model is as follows. For each label, an anchor point is chosen inside the label or on its boundary. Each label is placed such that the anchor point coincides with the corresponding point on the map. Furthermore, while the map fully rotates from 0 to 2π, the labels are placed horizontally according to the angle of the map. Our problem consists of finding the maximum scale factor for the labels such that the labels do not intersect, and determining the placing of the anchor points. We describe an O(n log n)-time and O(n)-space algorithm for the case where each anchor point is inside the label. Moreover, if the anchor points are on the boundaries, we also present an O(n log n)-time and O(n)-space exact and approximation algorithms for several label shapes.\n------------------------------\nThis is a preprint of an article intended for publication Journal of\nInformation Processing(JIP). This preprint should not be cited. This\narticle should be cited as: Journal of Information Processing Vol.25(2017) (online)\nDOI　http://dx.doi.org/10.2197/ipsjjip.25.572\n------------------------------","subitem_description_type":"Other"}]},"item_2_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"Map labeling is the problem of placing labels at corresponding graphical features on a map. There are two main optimization problems: the label number maximization problem and the label size maximization problem. In general, both problems are NP-hard for static maps. Recently, the widespread use of several applications, such as personal mapping systems, has increased the importance of dynamic maps and the label number maximization problem for dynamic cases has been studied. In this paper, we consider the label size maximization problem for points on rotating maps. Our model is as follows. For each label, an anchor point is chosen inside the label or on its boundary. Each label is placed such that the anchor point coincides with the corresponding point on the map. Furthermore, while the map fully rotates from 0 to 2π, the labels are placed horizontally according to the angle of the map. Our problem consists of finding the maximum scale factor for the labels such that the labels do not intersect, and determining the placing of the anchor points. We describe an O(n log n)-time and O(n)-space algorithm for the case where each anchor point is inside the label. Moreover, if the anchor points are on the boundaries, we also present an O(n log n)-time and O(n)-space exact and approximation algorithms for several label shapes.\n------------------------------\nThis is a preprint of an article intended for publication Journal of\nInformation Processing(JIP). This preprint should not be cited. This\narticle should be cited as: Journal of Information Processing Vol.25(2017) (online)\nDOI　http://dx.doi.org/10.2197/ipsjjip.25.572\n------------------------------","subitem_description_type":"Other"}]},"item_2_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographic_titles":[{"bibliographic_title":"情報処理学会論文誌"}],"bibliographicIssueDates":{"bibliographicIssueDate":"2017-08-15","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"8","bibliographicVolumeNumber":"58"}]},"relation_version_is_last":true,"weko_creator_id":"11"}}