Labeling points with weights

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

Research output: Chapter in Book/Conference proceedingConference contributionpeer-review

3 Citations (Scopus)


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 + ε), it runs in O n 2 /ε) time and uses O n/ε space. We also investigate some special cases.

Original languageEnglish
Title of host publicationAlgorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings
Number of pages13
Publication statusPublished - 2001
Externally publishedYes
Event12th International Symposium on Algorithms and Computation, ISAAC 2001 - Christchurch, New Zealand
Duration: 19 Dec 200121 Dec 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2223 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference12th International Symposium on Algorithms and Computation, ISAAC 2001
Country/TerritoryNew Zealand

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


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

Cite this