Spatial partitions of an information space are frequently used for data visualization. Weighted Voronoi diagrams are among the most popular ways of dividing a space into partitions. However, the problem of computing such a partition efficiently can be challenging. For example, a natural objective is to select the weights so as to force each Voronoi region to take on a pre-defined area, which might represent the relevance or market share of an informational object. In this paper, we present an easy and fast algorithm to compute these weights of the Voronoi diagrams. Unlike previous approaches whose convergence properties are not well-understood, we give a formulation to the problem based on convex optimization with excellent performance guarantees in theory and practice. We also show how our technique can be used to control the shape of these partitions. More specifically we show how to convert undesirable skinny and long regions into fat regions while maintaining the areas of the partitions. As an application, we use these to visualize the amount of website traffic for the top 101 websites.

Date Published: 3 February 2014
PDF: 8 pages
Proc. SPIE 9017, Visualization and Data Analysis 2014, 90170V (3 February 2014); doi: 10.1117/12.2042607

Published in SPIE Proceedings Vol. 9017:
Visualization and Data Analysis 2014
Pak Chung Wong; David L. Kao; Ming C. Hao; Chaomei Chen, Editor(s)