Point labeling with sliding labels

M.J. Kreveld, van, T. Strijk, A. Wolff

    Research output: Contribution to journalArticleAcademicpeer-review

    115 Citations (Scopus)
    2 Downloads (Pure)

    Abstract

    This paper discusses algorithms for labeling sets of points in the plane, where labels are not restricted to some finite number of positions. We show that continuously sliding labels allow more points to be labeled both in theory and in practice. We define six different models of labeling. We compare models by analyzing how many more points can receive labels under one model than another. We show that maximizing the number of labeled points is NP-hard in the most general of the new models. Nevertheless, we give a polynomial-time approximation scheme and a simple and efficient factor- approximation algorithm for each of the new models. Finally, we give experimental results based on the factor- approximation algorithm to compare the models in practice. We also compare this algorithm experimentally to other algorithms suggested in the literature.
    Original languageEnglish
    Pages (from-to)21-47
    Number of pages27
    JournalComputational Geometry
    Volume13
    Issue number1
    DOIs
    Publication statusPublished - 1999

    Fingerprint

    Dive into the research topics of 'Point labeling with sliding labels'. Together they form a unique fingerprint.

    Cite this