Point labeling with sliding labels

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

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    115 Citaten (Scopus)
    2 Downloads (Pure)


    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.
    Originele taal-2Engels
    Pagina's (van-tot)21-47
    Aantal pagina's27
    TijdschriftComputational Geometry
    Nummer van het tijdschrift1
    StatusGepubliceerd - 1999


    Duik in de onderzoeksthema's van 'Point labeling with sliding labels'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit