Computing Voronoi Treemaps: Faster, Simpler, and Resolution-independent

Simple item page
dc.contributor.authorNocaj, Arlinden_US
dc.contributor.authorBrandes, Ulriken_US
dc.contributor.editorS. Bruckner, S. Miksch, and H. Pfisteren_US
dc.date.accessioned2015-02-28T07:01:38Z
dc.date.available2015-02-28T07:01:38Z
dc.date.issued2012en_US
dc.description.abstractVoronoi 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 Ω(n2) time per iteration, with n the number of sites. We describe its implementation and present evidence that it is faster also in practice.en_US
dc.description.seriesinformationComputer Graphics Forumen_US
dc.description.volume31
dc.identifier.doi10.1111/j.1467-8659.2012.03078.x
dc.identifier.issn1467-8659en_US
dc.identifier.urihttps://doi.org/10.1111/j.1467-8659.2012.03078.xen_US
dc.publisherThe Eurographics Association and Blackwell Publishing Ltd.en_US
dc.titleComputing Voronoi Treemaps: Faster, Simpler, and Resolution-independenten_US
Files
Collections
31-Issue 3
EuroVis12: Eurographics Conference on Visualization