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(n 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.
%0 Journal Article
%1 sw-lpc-01
%A Strijk, Tycho
%A Wolff, Alexander
%D 2001
%J International Journal of Computational Geometry and Applications
%K automated_label_placement cartography myown packing_problem visualization
%N 2
%P 181--195
%R 10.1142/S0218195901000444
%T Labeling Points with Circles
%V 11
%X 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(n 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.
@article{sw-lpc-01,
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(n \log 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.},
added-at = {2024-02-18T09:53:56.000+0100},
author = {Strijk, Tycho and Wolff, Alexander},
biburl = {https://www.bibsonomy.org/bibtex/25ae93efd8622c47a3adc3385c2bbff16/awolff},
cites = {aks-lpmis-98, c-accgc-96, cms-esapf-95,
dlss-sdakp-95, dmmmz-mlg-97, ee-innfm-94,
f-agpsp-92, fpt-opcpa-81, fw-ppalm-91, il-nhsml-97,
kr-pcr-92, kt-ualgf-98, l-pftu-82, ms-ccclp-91,
ksw-plsl-99, ws-mlb-96, wwks-3rsgl-01, ZZZ},
confmonth = {apr},
doi = {10.1142/S0218195901000444},
interhash = {1e00f56d37148febe87ebb43df3a3d32},
intrahash = {5ae93efd8622c47a3adc3385c2bbff16},
journal = {International Journal of Computational Geometry and Applications},
keywords = {automated_label_placement cartography myown packing_problem visualization},
number = 2,
pages = {181--195},
pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/sw-lpc-01.pdf},
precedes = {dmm-pslsp-00},
succeeds = {dmmmz-mlg-97, sw-lpc-99},
timestamp = {2024-02-18T12:36:59.000+0100},
title = {Labeling Points with Circles},
volume = 11,
year = 2001
}