Dynamic point labeling is strongly PSPACE-hard

K. Buchin, D.H.P. Gerrits

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademic

49 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-hard to obtain 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
Titel29th European Workshop on Computational Geometry (EuroCG 2013, Braunschweig, Germany, March 17-20, 2013)
Pagina's241-244
StatusGepubliceerd - 2013

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

  • Citeer dit

    Buchin, K., & Gerrits, D. H. P. (2013). Dynamic point labeling is strongly PSPACE-hard. In 29th European Workshop on Computational Geometry (EuroCG 2013, Braunschweig, Germany, March 17-20, 2013) (blz. 241-244)