Labeling points with weights

Sheung Hung Poon, Chan Su Shin, Tycho Strijk, Takeaki Uno, Alexander Wolff

Research output: Journal PublicationArticlepeer-review

25 Citations (Scopus)

Abstract

Annotating maps, graphs, and diagrams with pieces of text is an important step in information visualization that is usually referred to as label placement. We define nine label-placement models for labeling points with axis-parallel rectangles given a weight for each point. There are two groups: fixed-position models and slider models. We aim to maximize the weight sum of those points that receive a label. We first compare our models by giving bounds for the ratios between the weights of maximum-weight labelings in different models. Then we present algorithms for labeling n points with unit-height rectangles. We show how an O(n\log n)-time factor-2 approximation algorithm and a PTAS for fixed-position models can be extended to handle the weighted case. Our main contribution is the first algorithm for weighted sliding labels. Its approximation factor is (2+\varepsilon), it runs in O(n 2/\varepsilon) time and uses O(n/\varepsilon) space. We show that other than for fixed-position models even the projection to one dimension remains NP-hard. For slider models we also investigate some special cases, namely (a) the number of different point weights is bounded, (b) all labels are unit squares, and (c) the ratio between maximum and minimum label height is bounded.

Original languageEnglish
Pages (from-to)341-362
Number of pages22
JournalAlgorithmica
Volume38
Issue number2
DOIs
Publication statusPublished - Nov 2003
Externally publishedYes

Keywords

  • Combinatorial optimization
  • Computational geometry
  • GIS
  • Job scheduling
  • Label placement
  • Maximum weight independent set
  • Sliding labels
  • Throughput maximization

ASJC Scopus subject areas

  • Computer Science (all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Labeling points with weights'. Together they form a unique fingerprint.

Cite this