Dynamic point labeling is strongly PSPACE-complete

K. Buchin, D.H.P. Gerrits

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (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.
Original languageEnglish
Title of host publicationAlgorithms and Computation (24th International Symposium, ISAAC 2013, Hong Kong, December 16-18, 2013. Proceedings)
EditorsL. Cai, S.-W. Cheng, T.-W. Lam
Place of PublicationBerlin
ISBN (Print)978-3-642-45029-7
Publication statusPublished - 2013
Event24th International Symposium on Algorithms and Computation (ISAAC 2013) - University of Hong Kong, Hong Kong, China
Duration: 16 Dec 201318 Dec 2013
Conference number: 24

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Conference24th International Symposium on Algorithms and Computation (ISAAC 2013)
Abbreviated titleISAAC 2013
CityHong Kong
Internet address


Dive into the research topics of 'Dynamic point labeling is strongly PSPACE-complete'. Together they form a unique fingerprint.

Cite this