Fast Dynamic Voronoi Treemaps - Fisher, Danyel; Lee, Huai-Ping; Sud, Avneesh (Proceedings of the 7th International Symposium on Voronoi Diagrams, 2010)
Abstract—The Voronoi Treemap is a space-ﬁlling treemap technique that relaxes the constraints of rectangular nodes. Its organic shapes maintain a one-to-one aspect ratio, are ﬂexible with their placement, allowing stable zooming and dynamic data values. In this paper, we present algorithms for efﬁcient computation and dynamic update of Voronoi Treemaps. Our GPGPU-based technique allows for rapid computation of centroidal Voronoi Diagrams, providing almost two orders of magnitude speedup over previous work. In addition, we present a hierarchical algorithm for stable updates. Finally, we demonstrate the application of Voronoi treemaps to real-world dynamic datasets, including interactive navigation.
This replaces the previous technical report, MSR-TR-2010-37