Optimal straight-line labels for island groups

Maps are used to solve a wide variety of tasks, ranging from navigation to analysis. Often, the quality of a map is directly related to the quality of its labelling. Consequently, a lot of research has focussed on the automatization of the labelling process. Surprisingly the (automated) labelling of island groups has received little attention so far. This is at least partially caused by the lack of cartographic principles. 31 Though extensive guidelines for map labelling exist, information on the labelling of groups of islands is surprisingly sparse. We define a formal framework for island labelling. The framework spawns a large series of unexplored computational geometry problems, which are interesting for the CG-community. In this paper we start by looking at a non-overlapping, straight label. We describe two algorithms for a straight-line label that is, or is not, allowed overlap with islands. Furthermore, we discus several extensions to these algorithms solving closely related problems.