Labeling points with weights

S.H. Poon, C.S. Shin, T. Strijk, A. Wolff

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    3 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 + e), it runs in O n 2 /e) time and uses O n/e space. We also investigate some special cases.
    Original languageEnglish
    Title of host publicationAlgorithms and computation : proceedings 12th international symposium, ISAAC 2001, Christchurch, New Zealand, december 19-21, 2001
    EditorsP. Eades, T. Takaoka
    Place of PublicationBerlin
    PublisherSpringer
    Pages610-622
    ISBN (Print)3-540-42985-9
    DOIs
    Publication statusPublished - 2001

    Publication series

    NameLecture Notes in Computer Science
    Volume2223
    ISSN (Print)0302-9743

    Fingerprint

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

    Cite this