Data Visualization Using Weighted Voronoi Diagrams

Introduction

A Voronoi diagram of a planar region and a set of points is a tessellation of into sub-regions based on proximity to the nearest point in :

The norm in the above expression is usually Euclidean, but may also be taken under the or 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.

Voronoi diagrams have been generalized in a number of ways by introducing a weight vector associated with the landmark points (Aurenhammer et al., 2013; Okabe et al., 2009); the tessellation 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

  

• •

  In a multiplicatively weighted Voronoi diagram, the tessellation satisfies

  

• •

  In a power Voronoi diagram, the tessellation satisfies