DYNAMIC POINT LABELING IS STRONGLY PSPACE-COMPLETE

DOI10.1142/S0218195914600127zbMath1331.68248OpenAlexW4250922312MaRDI QIDQ5261020

Kevin Buchin, Dirk H. P. Gerrits

Publication date: 1 July 2015

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218195914600127

zbMATH Keywords

complexity analysisPSPACE-hardnessdynamic label placement

Mathematics Subject Classification ID

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

Related Items (4)

Minimum Point-Overlap Labeling ⋮ A unified model and algorithms for temporal map labeling ⋮ Minimum point-overlap labelling* ⋮ Evaluation of Labeling Strategies for Rotating Maps

Cites Work

• Point labeling with sliding labels
• A better heuristic for orthogonal graph drawings
• Relationships between nondeterministic and deterministic tape complexities
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Optimizing active ranges for consistent dynamic map labeling

This page was built for publication: DYNAMIC POINT LABELING IS STRONGLY PSPACE-COMPLETE