Growing Balls in ℝd

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

BAHRDT, Daniel, Michael BECHER, Stefan FUNKE, Filip KRUMPE, André NUSSER, Martin SEYBOLD, Sabine STORANDT, 2017. Growing Balls in ℝd. ALENEX17. Barcelona, Spain, Jan 17, 2017 - Jan 18, 2017. In: FEKETE, Sándor, ed., Vijaya RAMACHANDRAN, ed.. 19th Workshop on Algorithm Engineering and Experiments 2017 (ALENEX17) : Barcelona, Spain, 17-18 January 2017. Red Hook, NY:Curran Associates, pp. 247-258. ISBN 978-1-5108-3586-3. Available under: doi: 10.1137/1.9781611974768.20

@inproceedings{Bahrdt2017Growi-43426, title={Growing Balls in ℝd}, year={2017}, doi={10.1137/1.9781611974768.20}, isbn={978-1-5108-3586-3}, address={Red Hook, NY}, publisher={Curran Associates}, booktitle={19th Workshop on Algorithm Engineering and Experiments 2017 (ALENEX17) : Barcelona, Spain, 17-18 January 2017}, pages={247--258}, editor={Fekete, Sándor and Ramachandran, Vijaya}, author={Bahrdt, Daniel and Becher, Michael and Funke, Stefan and Krumpe, Filip and Nusser, André and Seybold, Martin and Storandt, Sabine} }

Seybold, Martin Krumpe, Filip Bahrdt, Daniel 2018-10-02T14:11:53Z 2018-10-02T14:11:53Z Storandt, Sabine Nusser, André Krumpe, Filip Given a set of prioritized balls with fixed centers in ℝ<sup>d</sup> whose radii grow linearly over time, we want to compute the elimination order of these balls assuming that when two balls 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(Δ<sup>d</sup>n(log n + Δ<sup>d</sup>)) where Δ = r<sub>max</sub>/r<sub>min</sub> is the ratio between largest and smallest radius amongst the balls. For a natural application of this problem, namely drawing labels on the globe, we have Δ = O(1). An efficient implementation based on a spherical Delaunay triangulation allows to compute the elimination order for millions of labels on commodity Desktop hardware. Dealing with rounding error induced robustness issues turned out to be one of the major challenges in the implementation. Funke, Stefan Funke, Stefan Bahrdt, Daniel Becher, Michael Seybold, Martin Growing Balls in ℝ<sup>d</sup> 2017 Nusser, André Becher, Michael Storandt, Sabine eng

This item appears in the following Collection(s)

Search KOPS


My Account