In maps and diagrams, feature objects like points, lines, and polygons are often annotated by textual or graphical labels to convey information.
Textual labels are typically rectangular; graphical labels are often circular. Labeling a map manually is a very tedious task; computer scientists and cartographers are interested in designing efficient algorithms for automated label placement. In this presentation, we study a geometric optimization problem motivated by the application of labeling points with circles. We show that the Map Labeling with Uniform Circles
(MLUC) problem is NP-hard, and present two approximation algorithms with constant-factor performance guarantees.