Home // GEOProcessing 2015, The Seventh International Conference on Advanced Geographic Information Systems, Applications, and Services // View article

On Maxmin Active Range Problem for Weighted Consistent Dynamic Map Labeling

Authors:
Xiao Zhang
Sheung-Hung Poon
Minming Li
Victor C.S. Lee

Keywords: Geographic information systems; Dynamic map labeling; NP-hardness; Approximation algorithms

Abstract:
Geographical visualization systems, such as online maps, provide interactive operations on continuous zooming and panning. In consistent map labeling, users can navigate continuously through space without distracting behaviors such as popping and jumping. We study the consistent dynamic map labeling problem: Given a set of labels on the map and each label with a selectable active range and weight, find an appropriate active range for each label such that no two consistent labels intersect at any scale and the minimum weighted active range is maximized. It is named as maximizing minimum weighted active range problem (MMWAR). This study on MMWAR is of the theoretical and practical significance, since it is common that some labels in practical maps need better visibility than others. We investigate both the simple and general variants and present several theoretical results. For simple variants, simple 1D-MMWAR and 2D-MMWAR with proportional dilation are optimally solved in O(n log n) and O(n^2 log n), respectively. For general variants, we prove that general 1D-MMWAR with constant dilation and 2DMMWAR with proportional dilation are NP-complete. Moreover, we provide an O(log n)-approximation algorithm for the general 1D-MMWAR with proportional dilation, and an O (n^1/2)-factor approximation algorithm for the general 2D-MMWAR with proportional dilation. Our experimentation results show that on average, the approximation factors in our algorithms are much smaller than the worst-case upper bounds stated above, and our approximation algorithms run efficiently.

Pages: 32 to 37

Copyright: Copyright (c) IARIA, 2015

Publication date: February 22, 2015

Published in: conference

ISSN: 2308-393X

ISBN: 978-1-61208-383-4

Location: Lisbon, Portugal

Dates: from February 22, 2015 to February 27, 2015