TY - GEN

T1 - Labeling points with weights

AU - Poon, Sheung Hung

AU - Shin, Chan Su

AU - Strijk, Tycho

AU - Wolff, Alexander

PY - 2001

Y1 - 2001

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=71049195456&partnerID=8YFLogxK

U2 - 10.1007/3-540-45678-3_52

DO - 10.1007/3-540-45678-3_52

M3 - Conference contribution

AN - SCOPUS:71049195456

SN - 3540429859

SN - 9783540429852

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 610

EP - 622

BT - Algorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings

T2 - 12th International Symposium on Algorithms and Computation, ISAAC 2001

Y2 - 19 December 2001 through 21 December 2001

ER -