Publikation: Growing Balls in ℝd
Lade...
Dateien
Zu diesem Dokument gibt es keine Dateien.
Datum
2017
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
DOI (zitierfähiger Link)
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published
Erschienen 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, 2017, pp. 247-258. ISBN 978-1-5108-3586-3. Available under: doi: 10.1137/1.9781611974768.20
Zusammenfassung
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.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
Konferenz
ALENEX17, 17. Jan. 2017 - 18. Jan. 2017, Barcelona, Spain
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690
BAHRDT, Daniel, Michael BECHER, Stefan FUNKE, Filip KRUMPE, André NUSSER, Martin SEYBOLD, Sabine STORANDT, 2017. Growing Balls in ℝd. ALENEX17. Barcelona, Spain, 17. Jan. 2017 - 18. Jan. 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, 2017, pp. 247-258. ISBN 978-1-5108-3586-3. Available under: doi: 10.1137/1.9781611974768.20BibTex
@inproceedings{Bahrdt2017Growi-43426,
year={2017},
doi={10.1137/1.9781611974768.20},
title={Growing Balls in ℝ<sup>d</sup>},
isbn={978-1-5108-3586-3},
publisher={Curran Associates},
address={Red Hook, NY},
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}
}RDF
<rdf:RDF
xmlns:dcterms="http://purl.org/dc/terms/"
xmlns:dc="http://purl.org/dc/elements/1.1/"
xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
xmlns:bibo="http://purl.org/ontology/bibo/"
xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
xmlns:foaf="http://xmlns.com/foaf/0.1/"
xmlns:void="http://rdfs.org/ns/void#"
xmlns:xsd="http://www.w3.org/2001/XMLSchema#" >
<rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/43426">
<dc:contributor>Krumpe, Filip</dc:contributor>
<dcterms:title>Growing Balls in ℝ<sup>d</sup></dcterms:title>
<bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/43426"/>
<dc:contributor>Storandt, Sabine</dc:contributor>
<foaf:homepage rdf:resource="http://localhost:8080/"/>
<dc:creator>Bahrdt, Daniel</dc:creator>
<dc:contributor>Bahrdt, Daniel</dc:contributor>
<dc:contributor>Funke, Stefan</dc:contributor>
<dc:contributor>Nusser, André</dc:contributor>
<dc:creator>Nusser, André</dc:creator>
<dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-10-02T14:11:53Z</dcterms:available>
<dc:creator>Becher, Michael</dc:creator>
<dc:creator>Krumpe, Filip</dc:creator>
<dcterms:abstract xml:lang="eng">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.</dcterms:abstract>
<dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dc:creator>Storandt, Sabine</dc:creator>
<dc:language>eng</dc:language>
<dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-10-02T14:11:53Z</dc:date>
<dcterms:issued>2017</dcterms:issued>
<dc:contributor>Becher, Michael</dc:contributor>
<dc:contributor>Seybold, Martin</dc:contributor>
<void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
<dc:creator>Seybold, Martin</dc:creator>
<dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dc:creator>Funke, Stefan</dc:creator>
</rdf:Description>
</rdf:RDF>Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Nein
