کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
435179 689877 2016 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Approximation algorithms on consistent dynamic map labeling
ترجمه فارسی عنوان
الگوریتم تقریبی بر روی نقشه یابی پویا
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

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. This is also called the active range optimization (ARO) problem defined by Been et al. (2006) [2]. We propose approximation algorithms for several variants of this problem. For the simple ARO problem  , we provide a 3clog⁡n3clog⁡n-approximation algorithm for unit-width rectangular labels if there is a c  -approximation algorithm for the unit-width label placement problem in the plane; and a randomized polynomial-time O(log⁡nlog⁡log⁡n)O(log⁡nlog⁡log⁡n)-approximation algorithm for arbitrary rectangular labels. For the general ARO problem, we prove that it remains 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, and show that the bounds are tight.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 640, 9 August 2016, Pages 84–93
نویسندگان
, , ,