KOPS - The Institutional Repository of the University of Konstanz
# Growing Balls in ℝ<sup>d</sup>

Type of Publication: | Contribution to a conference collection |

Publication status: | Published |

Author: | Bahrdt, Daniel; Becher, Michael; Funke, Stefan; Krumpe, Filip; Nusser, André; Seybold, Martin; Storandt, Sabine |

Year of publication: | 2017 |

Conference: | ALENEX17, Jan 17, 2017 - Jan 18, 2017, Barcelona, Spain |

Published in: | 19th Workshop on Algorithm Engineering and Experiments 2017 (ALENEX17) : Barcelona, Spain, 17-18 January 2017 / Fekete, Sándor; Ramachandran, Vijaya (ed.). - Red Hook, NY : Curran Associates, 2017. - pp. 247-258. - ISBN 978-1-5108-3586-3 |

DOI (citable link): | https://dx.doi.org/10.1137/1.9781611974768.20 |

Summary: |
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(n^{2} log n) which we improve to expected O(Δ^{d}n(log n + Δ^{d})) where Δ = r_{max}/r_{min} 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. |

Subject (DDC): | 004 Computer Science |

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}
}