Circles in the Water: Towards Island Group Labeling

Abstract

Many algorithmic results are known for automated label placement on maps. However, algorithms to compute labels for groups of features, such as island groups, are largely missing. In this paper we address this issue by presenting new, efficient algorithms for island label placement in various settings. We consider straight-line and circular-arc labels that may or may not overlap a given set of islands. We concentrate on computing the line or circle that minimizes the maximum distance to the islands, measured by the closest distance. We experimentally test whether the generated labels are reasonable for various real-world island groups, and compare different options. The results are positive and validate our geometric formalizations.