Parametrized Runtimes for Label Tournaments

Abstract

Given an initial placement of n prioritized labels on a rotatable map, we consider the problem of determining which label subsets shall be displayed in zoomed-out views. This is modelled as a label tournament where the labels are represented as disks growing inversely proportional to a continuously decreasing zoom level. Due to that growth, labels would eventually overlap impairing the readability of the map. Hence whenever two labels touch, the one with lower priority gets eliminated. The goal of the paper is to design efficient algorithms that compute the elimination zoom level of each label. In previous work, it was shown that this can be accomplished within O (n5/3+E time and space. As this is practically infeasible for large n, algorithms with a parametrized running time depending not only on n but also on other aspects as the largest disk size or the spread of the disk centers were investigated. This paper contains two results: first, we introduce a new parameter C which denotes the number of different disk sizes in the input. In contrast to previously considered parameters, C is upper bounded by n. For the case that disk sizes and priorities coincide, we design an algorithm which runs in time O(nClogO(1)n). Experiments on label sets extracted from OpenStreetMaps demonstrate the applicability of our new approach. As a second result, we present improved running times for a known parametrization of the problem in higher dimensions.