Labeling Points with Weights
, , , and .
Proc. 17th European Workshop on Computational Geometry (EWCG'01), page 97--100. Berlin, (2001)

Annotating maps, graphs, and diagrams with pieces of text is an important step in information visualization that is usually refered 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 unit-height labels. We give an $O(nłog n)$-time factor-2 approximation algorithm for fixed-position models and the first algorithm for labeling weighted points with sliding labels. Its approximation factor is $(2+\varepsilon)$ and its runtime in $O(n^2/\varepsilon)$ for any $\varepsilon>0$.
  • @awolff
  • @dblp
  • @fink
This publication has not been reviewed yet.

rating distribution
average user rating0.0 out of 5.0 based on 0 reviews
    Please log in to take part in the discussion (add own reviews or comments).