Spatial partitioning algorithms for data visualization

Raghuveer Devulapalli; Mikael Quist; John Gunnar Carlsson

doi:10.1117/12.2042607

3 February 2014 Spatial partitioning algorithms for data visualization

Raghuveer Devulapalli, Mikael Quist, John Gunnar Carlsson

Proceedings Volume 9017, Visualization and Data Analysis 2014; 90170V (2014) https://doi.org/10.1117/12.2042607
Event: IS&T/SPIE Electronic Imaging, 2014, San Francisco, California, United States

Abstract

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.

Citation Download Citation

Raghuveer Devulapalli, Mikael Quist, and John Gunnar Carlsson "Spatial partitioning algorithms for data visualization", Proc. SPIE 9017, Visualization and Data Analysis 2014, 90170V (3 February 2014); https://doi.org/10.1117/12.2042607

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available