Consistent dynamic map labeling with fairness and importance

Xiao Zhang, Sheung Hung Poon, Shengxin Liu, Minming Li, Victor C.S. Lee

Research output: Journal PublicationArticlepeer-review

1 Citation (Scopus)

Abstract

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(n2log⁡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.

Original languageEnglish
Article number101892
JournalComputer Aided Geometric Design
Volume81
DOIs
Publication statusPublished - Aug 2020

Keywords

  • Active range assignment
  • Dynamic map labeling
  • Geographic information systems
  • Integer linear programming
  • NP-completeness

ASJC Scopus subject areas

  • Modelling and Simulation
  • Automotive Engineering
  • Aerospace Engineering
  • Computer Graphics and Computer-Aided Design

Fingerprint

Dive into the research topics of 'Consistent dynamic map labeling with fairness and importance'. Together they form a unique fingerprint.

Cite this