Point set labeling with specified positions

Abstract

Motivated by applications in cartography and computer graphics, we study a version of the map-labeling problem that we call the k-Position Map-Labeling Problem: given a set of points in the plane and, for each point, a set of up to k allowable positions, place uniform and nonintersecting labels of maximum size at each point in one of the allowable positions. This version combines an aesthetic criterion and a legibility criterion and comes close to actual practice while generalizing the fixed-point and slider models found in the literature. We then extend our approach to arbitrary positions, obtaining an algorithm that is easy to implement and also dramatically improves the best approximation bounds.