Data Visualization Using Weighted Voronoi Diagrams

Data Visualization Using Weighted Voronoi Diagrams

Raghuveer Devulapalli (University of Minnesota, USA), Neil Peterson (University of Minnesota, USA) and John Gunnar Carlsson (University of Southern California, USA)
Copyright: © 2015 |Pages: 24
DOI: 10.4018/978-1-4666-8465-2.ch007

Abstract

A Voronoi diagram is a standard spatial tessellation that partitions a domain into sub-regions based on proximity to a fixed set of landmark points. In order to maintain control over the size and shape of these sub-regions, a weighting scheme is often used, in which each landmark has a scalar value associated with it. This suggests a natural “inverse” problem: given a fixed set of landmark points in a given planar region and a set of “desired” areas, is it possible to calculate a set of weights so that each sub-region has a particular area? In this chapter, the authors give a fast scheme for determining these weights based on theory from convex optimization, which is then applied to a variety of problems in data visualization.
Chapter Preview
Top

Introduction

A Voronoi diagram of a planar region 978-1-4666-8465-2.ch007.m01 and a set of points 978-1-4666-8465-2.ch007.m02 is a tessellation of 978-1-4666-8465-2.ch007.m03 into 978-1-4666-8465-2.ch007.m04 sub-regions 978-1-4666-8465-2.ch007.m05 based on proximity to the nearest point in 978-1-4666-8465-2.ch007.m06:

The norm 978-1-4666-8465-2.ch007.m08 in the above expression is usually Euclidean, but may also be taken under the 978-1-4666-8465-2.ch007.m09 or 978-1-4666-8465-2.ch007.m10 norm, for example (Lee & Wong, 1980). Voronoi diagrams are widely applied in many different domains, such as data compression, facility location, robotics, and air traffic control, to name a few. Indeed, such structures are useful and intuitive for modelling many different kinds of spatial interactions: for example, if the points represent stores that are otherwise identical, then the Voronoi diagram describes the market regions for those stores, inasmuch as customers will prefer whichever store is closest to them. Voronoi diagrams are also of fundamental importance in classification: if the points represent reference data such as documents or images, then the Voronoi diagram describes the set of all “query” data that are most closely associated with a particular reference point. Figure 1a shows an example of a Voronoi diagram.

Figure 1.

A standard Voronoi diagram (a) and three weighted variants (b-d)of a set of points in the square.

978-1-4666-8465-2.ch007.f01

Voronoi diagrams have been generalized in a number of ways by introducing a weight vector978-1-4666-8465-2.ch007.m11 associated with the landmark points (Aurenhammer et al., 2013; Okabe et al., 2009); the tessellation 978-1-4666-8465-2.ch007.m12 then depends on these weights as well. The authors per this chapter consider three weighting schemes:

  • In an additively weighted Voronoi diagram, the tessellation satisfies

    978-1-4666-8465-2.ch007.m13

it can be shown that the boundaries between sub-regions are always hyperbolic arcs and that all sub-regions are connected.
  • In a multiplicatively weighted Voronoi diagram, the tessellation satisfies

    978-1-4666-8465-2.ch007.m14

it can be shown that the boundaries between sub-regions are always circular arcs.
  • In a power Voronoi diagram, the tessellation satisfies

    978-1-4666-8465-2.ch007.m15

it can be shown that the boundaries between sub-regions are always line segments and that all sub-regions are convex.

Complete Chapter List

Search this Book:
Reset