Computing Voronoi Treemaps: Faster, Simpler, and Resolution-independent
作者： Arlind Nocaj , Ulrik Brandes
DOI: 10.1111/J.1467-8659.2012.03078.X
关键词:
摘要: Voronoi treemaps represent hierarchies as nested polygons. We here show that, contrary to the apparent popular belief, utilization of an algorithm for weighted diagrams is not only feasible, but also more efficient than previous low-resolution approximations, even when latter are implemented on graphics hardware. More precisely, we propose instantiation Lloyd's method centroidal with Aurenhammer's power that yields running in 𝒪(n log n) rather Ω(n2) time per iteration, n number sites. describe its implementation and present evidence it faster practice. © 2012 Wiley Periodicals, Inc.
uni-konstanz.de
sci-hub.se 参考文章(26)
Ben Shneiderman, Treemaps for space-constrained visualization of hierarchies ,(2005)
Cristina N. Vasconcelos, Asla Sá, Paulo Cezar Carvalho, Marcelo Gattass, Lloyd’s Algorithm on GPU Advances in Visual Computing. pp. 953- 964 ,(2008) , 10.1007/978-3-540-89639-5_91
A. M. Day, The implementation of an algorithm to find the convex hull of a set of three-dimensional points ACM Transactions on Graphics. ,vol. 9, pp. 105- 132 ,(1990) , 10.1145/77635.77640
Guodong Rong, Yang Liu, Wenping Wang, Xiaotian Yin, X D Gu, Xiaohu Guo, GPU-Assisted Computation of Centroidal Voronoi Tessellation IEEE Transactions on Visualization and Computer Graphics. ,vol. 17, pp. 345- 356 ,(2011) , 10.1109/TVCG.2010.53
Bernard Chazelle, Jiří Matoušek, Derandomizing an output-sensitive convex hull algorithm in three dimensions Computational Geometry: Theory and Applications. ,vol. 5, pp. 27- 32 ,(1995) , 10.1016/0925-7721(94)00018-Q
Herbert Edelsbrunner, Algorithms in Combinatorial Geometry ,(1987)
Avneesh Sud, Danyel Fisher, Huai-Ping Lee, Fast Dynamic Voronoi Treemaps international symposium on voronoi diagrams in science and engineering. pp. 85- 94 ,(2010) , 10.1109/ISVD.2010.16
F. P. Preparata, S. J. Hong, Convex hulls of finite sets of points in two and three dimensions Communications of the ACM. ,vol. 20, pp. 87- 93 ,(1977) , 10.1145/359423.359430
Joseph O'Rourke, Chi-Bin Chien, Thomas Olson, David Naddor, A New Linear Algorithm for Intersecting Convex Polygons Computer Graphics and Image Processing. ,vol. 19, pp. 384- 391 ,(1982) , 10.1016/0146-664X(82)90023-5
F. Aurenhammer, Power diagrams: properties, algorithms and applications SIAM Journal on Computing. ,vol. 16, pp. 78- 96 ,(1987) , 10.1137/0216006