Approximation algorithms on consistent dynamic map labeling

Chung Shou Liao, Chih Wei Liang, Sheung Hung Poon

Research output: Chapter in Book/Conference proceedingConference contributionpeer-review

4 Citations (Scopus)


We consider the dynamic map labeling problem: given a set of rectangular labels on the map, the goal is to appropriately select visible ranges for all the labels such that no two consistent labels overlap at every scale and the sum of total visible ranges is maximized. We propose approximation algorithms for several variants of this problem. For the simple ARO problem, we provide a 3c logn-approximation algorithm for the unit-width rectangular labels if there is a c-approximation algorithm for unit-width label placement problem in the plane; and a randomized polynomial-time O(logn loglogn)-approximation algorithm for arbitrary rectangular labels. For the general ARO problem, we prove that it is NP-complete even for congruent square labels with equal selectable scale range. Moreover, we contribute 12-approximation algorithms for both arbitrary square labels and unit-width rectangular labels, and a 6-approximation algorithm for congruent square labels.

Original languageEnglish
Title of host publicationFrontiers in Algorithmics - 8th International Workshop, FAW 2014, Proceedings
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783319080154
Publication statusPublished - 2014
Externally publishedYes
Event8th International Frontiers of Algorithmics Workshop, FAW 2014 - Zhangjiajie, China
Duration: 28 Jun 201430 Jun 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8497 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference8th International Frontiers of Algorithmics Workshop, FAW 2014

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Approximation algorithms on consistent dynamic map labeling'. Together they form a unique fingerprint.

Cite this