Labeling points with weights

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

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    3 Citaten (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 + e), it runs in O n 2 /e) time and uses O n/e space. We also investigate some special cases.
    Originele taal-2Engels
    TitelAlgorithms and computation : proceedings 12th international symposium, ISAAC 2001, Christchurch, New Zealand, december 19-21, 2001
    RedacteurenP. Eades, T. Takaoka
    Plaats van productieBerlin
    ISBN van geprinte versie3-540-42985-9
    StatusGepubliceerd - 2001

    Publicatie series

    NaamLecture Notes in Computer Science
    ISSN van geprinte versie0302-9743


    Duik in de onderzoeksthema's van 'Labeling points with weights'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit