Given a set of prioritized balls with fixed centers in ℝd 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(n2 log n) which we improve to expected O(Δdn(log n + Δd)) where Δ = rmax/rmin 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.
%0 Conference Paper
%1 conf/alenex/BahrdtBFKNSS17
%A Bahrdt, Daniel
%A Becher, Michael
%A Funke, Stefan
%A Krumpe, Filip
%A Nusser, André
%A Seybold, Martin
%A Storandt, Sabine
%B Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX)
%D 2017
%E Fekete, Sándor P.
%E Ramachandran, Vijaya
%I SIAM
%K 2017 B06 from:leonkokkoliadis sfbtrr161 visus visus:becherml
%P 247-258
%R 10.1137/1.9781611974768.20
%T Growing Balls in ℝd
%U https://doi.org/10.1137/1.9781611974768.20
%X Given a set of prioritized balls with fixed centers in ℝd 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(n2 log n) which we improve to expected O(Δdn(log n + Δd)) where Δ = rmax/rmin 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.
%@ 978-1-61197-476-8
@inproceedings{conf/alenex/BahrdtBFKNSS17,
abstract = {Given a set of prioritized balls with fixed centers in ℝd 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(n2 log n) which we improve to expected O(Δdn(log n + Δd)) where Δ = rmax/rmin 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.},
added-at = {2020-10-09T12:31:47.000+0200},
author = {Bahrdt, Daniel and Becher, Michael and Funke, Stefan and Krumpe, Filip and Nusser, André and Seybold, Martin and Storandt, Sabine},
biburl = {https://puma.ub.uni-stuttgart.de/bibtex/2bc66a08176ebc959fbc7c4d385750736/mueller},
booktitle = {Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX)},
description = {Growing Balls in ℝd},
doi = {10.1137/1.9781611974768.20},
editor = {Fekete, Sándor P. and Ramachandran, Vijaya},
ee = {http://dx.doi.org/10.1137/1.9781611974768.20},
interhash = {f793a87d2429890d29bf509e62132988},
intrahash = {bc66a08176ebc959fbc7c4d385750736},
isbn = {978-1-61197-476-8},
keywords = {2017 B06 from:leonkokkoliadis sfbtrr161 visus visus:becherml},
pages = {247-258},
publisher = {SIAM},
timestamp = {2020-10-09T10:31:47.000+0200},
title = {Growing Balls in ℝd},
url = {https://doi.org/10.1137/1.9781611974768.20},
year = 2017
}
