Aufgrund von Vorbereitungen auf eine neue Version von KOPS, können derzeit keine Publikationen eingereicht werden. (Due to preparations for a new version of KOPS, no publications can be submitted currently.)
Type of Publication: | Journal article |
URI (citable link): | http://nbn-resolving.de/urn:nbn:de:bsz:352-198930 |
Author: | Nocaj, Arlind; Brandes, Ulrik |
Year of publication: | 2012 |
Published in: | Computer Graphics Forum ; 31 (2012), 3pt1. - pp. 855-864. - ISSN 0167-7055. - eISSN 1467-8659 |
DOI (citable link): | https://dx.doi.org/10.1111/j.1467-8659.2012.03078.x |
Summary: |
Voronoi treemaps represent hierarchies as nested polygons. We here show that, contrary to the apparent popular belief, utilization of an algorithm for weighted Voronoi diagrams is not only feasible, but also more efficient than previous low-resolution approximations, even when the latter are implemented on graphics hardware. More precisely, we propose an instantiation of Lloyd's method for centroidal Voronoi diagrams with Aurenhammer's algorithm for power diagrams that yields an algorithm running in O(n log n) rather than Ω(n²) time per iteration, with n the number of sites. We describe its implementation and present evidence that it is faster also in practice.
|
Subject (DDC): | 004 Computer Science |
Link to License: | In Copyright |
Bibliography of Konstanz: | Yes |
NOCAJ, Arlind, Ulrik BRANDES, 2012. Computing Voronoi Treemaps : Faster, Simpler, and Resolution-independent. In: Computer Graphics Forum. 31(3pt1), pp. 855-864. ISSN 0167-7055. eISSN 1467-8659. Available under: doi: 10.1111/j.1467-8659.2012.03078.x
@article{Nocaj2012Compu-19893, title={Computing Voronoi Treemaps : Faster, Simpler, and Resolution-independent}, year={2012}, doi={10.1111/j.1467-8659.2012.03078.x}, number={3pt1}, volume={31}, issn={0167-7055}, journal={Computer Graphics Forum}, pages={855--864}, author={Nocaj, Arlind and Brandes, Ulrik} }
<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/rdf/resource/123456789/19893"> <dcterms:abstract xml:lang="deu">Voronoi treemaps represent hierarchies as nested polygons. We here show that, contrary to the apparent popular belief, utilization of an algorithm for weighted Voronoi diagrams is not only feasible, but also more efficient than previous low-resolution approximations, even when the latter are implemented on graphics hardware. More precisely, we propose an instantiation of Lloyd's method for centroidal Voronoi diagrams with Aurenhammer's algorithm for power diagrams that yields an algorithm running in O(n log n) rather than Ω(n²) time per iteration, with n the number of sites. We describe its implementation and present evidence that it is faster also in practice.</dcterms:abstract> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/19893/2/nb-cvt-12.pdf"/> <dcterms:bibliographicCitation>Publ. in: Computer Graphics Forum ; 31 (2012), 3pt1. - pp. 855-864</dcterms:bibliographicCitation> <dcterms:title>Computing Voronoi Treemaps : Faster, Simpler, and Resolution-independent</dcterms:title> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2012-08-02T06:48:28Z</dc:date> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:rights>terms-of-use</dc:rights> <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/19893"/> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2013-07-31T22:25:04Z</dcterms:available> <dc:language>deu</dc:language> <dc:contributor>Nocaj, Arlind</dc:contributor> <dc:contributor>Brandes, Ulrik</dc:contributor> <dc:creator>Nocaj, Arlind</dc:creator> <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/> <dcterms:issued>2012</dcterms:issued> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/19893/2/nb-cvt-12.pdf"/> <dc:creator>Brandes, Ulrik</dc:creator> </rdf:Description> </rdf:RDF>
nb-cvt-12.pdf | 941 |