by Arlind Nocaj, Ulrik Brandes
Abstract:
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.
Reference:
Arlind Nocaj, Ulrik Brandes, "Computing Voronoi Treemaps: Faster, Simpler, and Resolution-independent", Computer Graphics Forum, vol. 31, no. 3, June 2012, pp. 855-864 (Best Paper Award).
Bibtex Entry:
@article {nb-cvt-12
, author = {Arlind Nocaj and Ulrik Brandes}
, title = {Computing Voronoi Treemaps: Faster, Simpler, and Resolution-independent}
, journal = {Computer Graphics Forum}
, volume = {31}
, number = {3}
, pages = {855--864}
, year = {2012}
, month = {June}
, doi = {10.1111/j.1467-8659.2012.03078.x}
, url = {http://algo.uni-konstanz.de/publications/nb-cvt-12.pdf}
, comment= {<a href="http://www.cg.tuwien.ac.at/eurovis2012/awards/best-paper-award/">Best Paper Award</a>}
, abstract = {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.}
}