Crushing Disks Efficiently

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

FUNKE, Stefan, Filip KRUMPE, Sabine STORANDT, 2016. Crushing Disks Efficiently. 27th International Workshop, IWOCA 2016. Helsinki, Finland, Aug 17, 2016 - Aug 19, 2016. In: MÄKINEN, Veli, ed. and others. Combinatorial Algorithms : 27th International Workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016, proceedings. Cham:Springer, pp. 43-54. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-319-44542-7. Available under: doi: 10.1007/978-3-319-44543-4_4

@inproceedings{Funke2016-08-09Crush-43521, title={Crushing Disks Efficiently}, year={2016}, doi={10.1007/978-3-319-44543-4_4}, number={9843}, isbn={978-3-319-44542-7}, issn={0302-9743}, address={Cham}, publisher={Springer}, series={Lecture Notes in Computer Science}, booktitle={Combinatorial Algorithms : 27th International Workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016, proceedings}, pages={43--54}, editor={Mäkinen, Veli}, author={Funke, Stefan and Krumpe, Filip and Storandt, Sabine} }

2018-10-15T09:44:57Z Krumpe, Filip Funke, Stefan Storandt, Sabine Given a set of prioritized disks with fixed centers in R<sup>2</sup> whose radii grow linearly over time, we are interested in computing an elimination order of these disks assuming that when two disks touch, the one with lower priority is ‘crushed’. A straightforward algorithm has running time O(n<sup>2</sup>log n) which we improve to expected O(n(log<sup>6</sup>n+Δ<sup>2</sup>log<sup>2</sup>n+Δ<sup>4</sup>log n)) where Δ is the ratio between largest and smallest radii amongst the disks. For a very natural application of this problem in the map rendering domain, we have Δ=O(1). Crushing Disks Efficiently Storandt, Sabine 2018-10-15T09:44:57Z eng Funke, Stefan 2016-08-09 Krumpe, Filip

This item appears in the following Collection(s)

Search KOPS


Browse

My Account