Dynamic Point Labeling is Strongly PSPACE-Complete

DOI10.1007/978-3-642-45030-3_25zbMATH Open1331.68247OpenAlexW2187114588MaRDI QIDQ2872091FDOQ2872091

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

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

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)

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)