{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,12]],"date-time":"2025-12-12T13:26:51Z","timestamp":1765546011213},"reference-count":5,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2014,12]]},"abstract":"<jats:p> An important but strongly NP-hard problem in automated cartography is how to best place textual labels for point features on a static map. We examine the complexity of various generalizations of this problem for dynamic and\/or interactive maps. Specifically, we show that it is strongly PSPACE-complete to decide whether there is a smooth dynamic labeling (function from time to static labelings) when the points move, when points are added and removed, or when the user pans, rotates, and\/or zooms their view of the points. In doing so we develop a framework from which a wide variety of labeling hardness results can be obtained, including (next to the PSPACE-hardness results) both known and new results on the NP-hardness of static labeling. <\/jats:p>","DOI":"10.1142\/s0218195914600127","type":"journal-article","created":{"date-parts":[[2015,5,25]],"date-time":"2015-05-25T15:11:58Z","timestamp":1432566718000},"page":"373-395","source":"Crossref","is-referenced-by-count":7,"title":["DYNAMIC POINT LABELING IS STRONGLY PSPACE-COMPLETE"],"prefix":"10.1142","volume":"24","author":[{"given":"KEVIN","family":"BUCHIN","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, Den Dolech 2, 5600 MB Eindhoven, The Netherlands"}]},{"given":"DIRK H. P.","family":"GERRITS","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, Den Dolech 2, 5600 MB Eindhoven, The Netherlands"}]}],"member":"219","published-online":{"date-parts":[[2015,5,25]]},"reference":[{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(99)00005-X"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2009.03.006"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.05.008"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(97)00026-6"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80006-X"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195914600127","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T17:41:01Z","timestamp":1565199661000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195914600127"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12]]},"references-count":5,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2015,5,25]]},"published-print":{"date-parts":[[2014,12]]}},"alternative-id":["10.1142\/S0218195914600127"],"URL":"https:\/\/doi.org\/10.1142\/s0218195914600127","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12]]}}}