# Labeling Points with Circles

###
Alexander Wolff

Institut für Informatik

Freie Universität Berlin

Takustr. 9, D-14195 Berlin

email: awolff@inf.fu-berlin.de

Tycho Strijk

Department of Computer Science

Utrecht University

email: tycho@cs.uu.nl

Report B 99-08

April 1999

We present a new algorithm for labeling points with circles of equal size. Our algorithm maximizes 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.

Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-99-08.ps.gz