Dynamic Point Labeling is Strongly PSPACE-Complete

DOI10.1007/978-3-642-45030-3_25MaRDI QIDQ2872091zbMATH OpenOpenAlexFDO

Authors Kevin Buchin, Dirk H. P. Gerrits

Publication date 14 January 2014

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-45030-3_25

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Dynamic point labeling is strongly PSPACE-complete
• Approximation algorithms on consistent dynamic map labeling
• Approximation Algorithms on Consistent Dynamic Map Labeling
• Searching dynamic point sets in spaces with bounded doubling dimension
• Optimal algorithm for a special point-labeling problem
• scientific article; zbMATH DE number 2089214
• EFFICIENT APPROXIMATION ALGORITHMS FOR TWO-LABEL POINT LABELING
• scientific article; zbMATH DE number 1796965
• Dynamic well-spaced point sets
• Dynamic well-spaced point sets

Cited in

(1)

• Dynamic point labeling is strongly PSPACE-complete

This page was built for publication: Dynamic Point Labeling is Strongly PSPACE-Complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2872091)