Consistent dynamic map labeling with fairness and importance

Geographical visualization systems, such as online maps, provide interactive operations of continuous zooming and panning. With consistent dynamic map labeling, users can navigate continuously in the map areas such that labels are not allowed to exhibit abrupt change in terms of their positions or sizes, and labels should not suddenly disappear or reappear when zooming in or pop up when zooming out. However, existing works on consistent dynamic map labeling only study the problem of optimizing overall visibility of labels across all zooming scales, and overlook the fairness and importance issues when labels are selected for showing at different scales. Such issues are in fact important ones, and need to be addressed. In this paper, we propose to assign weights to labels to reveal their corresponding importance and study the novel problem of maximizing minimum weighted active range (MMWAR), in which we compute an active range assignment such that (1) no two active ranges overlap and (2) the minimum weighted active range height is maximized. In particular, we study the simple MMWAR problem by restricting the active ranges such that a label is never deselected when zooming in, and present optimal O(n²log⁡n) time algorithms for 1D and 2D cases, where n is the number of labels. We present an O(nlog⁡n) time algorithm for simple MMWAR in 1D of congruent case. Further, we generalize the simple MMWAR problem to the ex-simple MMWAR problem, in which the starting active scale is not fixed to be zero anymore. On the problem complexity side, we prove that the ex-simple MMWAR problem in 2D is NP-hard, even if all extrusions are congruent square pyramids. Next, we propose two fast algorithms for the ex-simple MMWAR problem in which all labels have the same weight. Then, we present an Integer Linear Programming (ILP) formulation for computing the optimal solutions for several variants of the MMWAR problem. Finally, we evaluate the performance of our proposed algorithms on real world dataset experimentally.