Dynamic point labeling is strongly PSPACE-complete

Autor:	Buchin, K., Gerrits, D.H.P., Cai, L., Cheng, S.-W., Lam, T.-W.
Přispěvatelé:	Algorithms
Jazyk:	angličtina
Rok vydání:	2013
Předmět:	Discrete mathematics Constraint graph ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION Point (geometry) Function (mathematics) PSPACE-complete PSPACE Mathematics
Zdroj:	Algorithms and Computation ISBN: 9783642450297 ISAAC Algorithms and Computation (24th International Symposium, ISAAC 2013, Hong Kong, December 16-18, 2013. Proceedings), 262-272 STARTPAGE=262;ENDPAGE=272;TITLE=Algorithms and Computation (24th International Symposium, ISAAC 2013, Hong Kong, December 16-18, 2013. Proceedings)
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::00aade43d1930d91f613c1f4b637cbfb https://research.tue.nl/en/publications/d8b10a74-17ba-4acc-bc1e-9af737b17f3c Zobrazit plný text záznamu