Parametrized Runtimes for Label Tournaments

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

FUNKE, Stefan, Sabine STORANDT, 2019. Parametrized Runtimes for Label Tournaments. 13th International Conference, COCOA 2019. Xiamen, China, Dec 13, 2019 - Dec 15, 2019. In: LI, Yingshu, ed., Mihaela CARDEI, ed., Yan HUANG, ed.. Combinatorial Optimization and Applications : 13th International Conference, COCOA 2019, Xiamen, China, December 13-15, 2019, Proceedings. Cham:Springer International Publishing, pp. 181-196. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-030-36411-3. Available under: doi: 10.1007/978-3-030-36412-0_15

@inproceedings{Funke2019-11-23Param-48220, title={Parametrized Runtimes for Label Tournaments}, year={2019}, doi={10.1007/978-3-030-36412-0_15}, number={11949}, isbn={978-3-030-36411-3}, issn={0302-9743}, address={Cham}, publisher={Springer International Publishing}, series={Lecture Notes in Computer Science}, booktitle={Combinatorial Optimization and Applications : 13th International Conference, COCOA 2019, Xiamen, China, December 13-15, 2019, Proceedings}, pages={181--196}, editor={Li, Yingshu and Cardei, Mihaela and Huang, Yan}, author={Funke, Stefan and Storandt, Sabine} }

Storandt, Sabine 2020-01-14T12:20:56Z 2019-11-23 Storandt, Sabine eng Funke, Stefan Parametrized Runtimes for Label Tournaments 2020-01-14T12:20:56Z 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 (n<sup>5/3+E</sup> 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(nClog<sup>O(1)</sup>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. Funke, Stefan

This item appears in the following Collection(s)

Search KOPS


My Account