Name
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 dene nine label-placement models for label- ing points with axis-parallel rectangles given a weight for each point. There are two groups; xed-p osition models and slider models. We aim to maximize the weight sum of those points that receive a label. We rst compare our models by giving bounds for the ratios between the weights of maximum-weight labelings in dieren t 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 xed-p osition models can be extended to handle the weighted case. Our main contribution is the rst algorithm for weighted sliding labels. Its approximation factor is (2 + "), it runs in O(n2=") time and uses O(n=") space. We also investigate some special cases. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1007/3-540-45678-3_52 | International Symposium on Algorithms and Computation |
Keywords | Field | DocType |
Computational geometry,GIS,Label placement,Sliding labels,Combinatorial optimization,Job scheduling,Throughput
maximization,Maximum weight independent set | Graph theory,Discrete mathematics,Approximation algorithm,Data visualization,Combinatorics,Information visualization,Scheduling (computing),Computational geometry,Combinatorial optimization,Time complexity,Mathematics,Distributed computing | Conference |
Volume | Issue | ISSN |
38 | 2 | 0302-9743 |
ISBN | Citations | PageRank |
3-540-42985-9 | 5 | 0.57 |
References | Authors | |
13 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sheung-Hung Poon | 1 | 231 | 29.36 |
| Chan-su Shin | 2 | 206 | 26.76 |
| Tycho Strijk | 3 | 203 | 14.26 |
| Alexander Wolff | 4 | 222 | 22.66 |