Dynamic point labeling is strongly PSPACE-complete

K. Buchin, D.H.P. Gerrits

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

2 Citaten (Scopus)
1 Downloads (Pure)

Samenvatting

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.
Originele taal-2Engels
TitelAlgorithms and Computation (24th International Symposium, ISAAC 2013, Hong Kong, December 16-18, 2013. Proceedings)
RedacteurenL. Cai, S.-W. Cheng, T.-W. Lam
Plaats van productieBerlin
UitgeverijSpringer
Pagina's262-272
ISBN van geprinte versie978-3-642-45029-7
DOI's
StatusGepubliceerd - 2013
Evenement24th International Symposium on Algorithms and Computation (ISAAC 2013) - University of Hong Kong, Hong Kong, China
Duur: 16 dec 201318 dec 2013
Congresnummer: 24
http://www.cs.hku.hk/isaac2013/

Publicatie series

NaamLecture Notes in Computer Science
Volume8283
ISSN van geprinte versie0302-9743

Congres

Congres24th International Symposium on Algorithms and Computation (ISAAC 2013)
Verkorte titelISAAC 2013
LandChina
StadHong Kong
Periode16/12/1318/12/13
Ander24th International Symposium on Algorithms and Computation
Internet adres

Vingerafdruk Duik in de onderzoeksthema's van 'Dynamic point labeling is strongly PSPACE-complete'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Buchin, K., & Gerrits, D. H. P. (2013). Dynamic point labeling is strongly PSPACE-complete. In L. Cai, S-W. Cheng, & T-W. Lam (editors), Algorithms and Computation (24th International Symposium, ISAAC 2013, Hong Kong, December 16-18, 2013. Proceedings) (blz. 262-272). (Lecture Notes in Computer Science; Vol. 8283). Springer. https://doi.org/10.1007/978-3-642-45030-3_25