Labeling points with circles

T. Strijk; A. Wolff

doi:10.1142/S0218195901000444

Labeling points with circles

T. Strijk
, A. Wolff

Research output: Contribution to journal › Article › Academic › peer-review

21 Citations (Scopus)

Abstract

We present a new algorithm for labeling points with circles of equal size. Our algorithm tries to maximize the label size. It improves the approximation factor of the only known algorithm for this problem by more than 50% to about 1/20. At the same time, our algorithm keeps the O(nlog n) time bound of its predecessor. In addition, we show that the decision problem is NP-hard and that it is NP-hard to approximate the maximum label size beyond a certain constant factor.

Original language	English
Pages (from-to)	181-195
Journal	International Journal of Computational Geometry and Applications
Volume	11
Issue number	2
DOIs	https://doi.org/10.1142/S0218195901000444
Publication status	Published - 2001

Access to Document

10.1142/S0218195901000444

Cite this

@article{026ec81f7fbc44cfae3405959ef5fb4f,

title = "Labeling points with circles",

abstract = "We present a new algorithm for labeling points with circles of equal size. Our algorithm tries to maximize the label size. It improves the approximation factor of the only known algorithm for this problem by more than 50\% to about 1/20. At the same time, our algorithm keeps the O(nlog n) time bound of its predecessor. In addition, we show that the decision problem is NP-hard and that it is NP-hard to approximate the maximum label size beyond a certain constant factor.",

author = "T. Strijk and A. Wolff",

year = "2001",

doi = "10.1142/S0218195901000444",

language = "English",

volume = "11",

pages = "181--195",

journal = "International Journal of Computational Geometry and Applications",

issn = "0218-1959",

publisher = "World Scientific",

number = "2",

}

TY - JOUR

T1 - Labeling points with circles

AU - Strijk, T.

AU - Wolff, A.

PY - 2001

Y1 - 2001

N2 - We present a new algorithm for labeling points with circles of equal size. Our algorithm tries to maximize the label size. It improves the approximation factor of the only known algorithm for this problem by more than 50% to about 1/20. At the same time, our algorithm keeps the O(nlog n) time bound of its predecessor. In addition, we show that the decision problem is NP-hard and that it is NP-hard to approximate the maximum label size beyond a certain constant factor.

AB - We present a new algorithm for labeling points with circles of equal size. Our algorithm tries to maximize the label size. It improves the approximation factor of the only known algorithm for this problem by more than 50% to about 1/20. At the same time, our algorithm keeps the O(nlog n) time bound of its predecessor. In addition, we show that the decision problem is NP-hard and that it is NP-hard to approximate the maximum label size beyond a certain constant factor.

U2 - 10.1142/S0218195901000444

DO - 10.1142/S0218195901000444

M3 - Article

SN - 0218-1959

VL - 11

SP - 181

EP - 195

JO - International Journal of Computational Geometry and Applications

JF - International Journal of Computational Geometry and Applications

IS - 2

ER -

Labeling points with circles

Abstract

Access to Document

Fingerprint

Cite this