Dynamic point labeling is strongly PSPACE-hard

K. Buchin, D.H.P. Gerrits

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

8 Citaten (Scopus)
1 Downloads (Pure)


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. Keywords: Dynamic label placement; complexity analysis; PSPACE-hardness
Originele taal-2Engels
Pagina's (van-tot)373-395
TijdschriftInternational Journal of Computational Geometry and Applications
Nummer van het tijdschrift4
StatusGepubliceerd - 2014

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

Citeer dit