What-if analysis for point data sets using generalised Voronoi diagrams

Ickjai Lee^a and Mark Gahegan^b
^aDepartment of Computer Science & Software Engineering, The University of Newcastle, Callaghan, NSW 2308, Australia
^bDepartment of Geography, The Pennsylvania State University, Walker Building, University Park, PA 16802, USA
E-mail: ijlee@cs.newcastle.edu.au, mark@geog.psu.edu

Abstract

The main objective of "what-if" analysis for decision making is to instantly explore scenarios as soon as changes are suggested. That is, we must achieve interactive spatial analysis successfully. This is only possible if spatial proximity is properly modelled and updates are fast because effectively constrained to local area.

Ordinary Voronoi diagrams have gained popularity to model discrete point data sets, because they achieve the two issues above, namely, they uniquely model spatial proximity in points and algorithms and data structures exist for fast dynamic update using local spatial proximity. The information of spatial proximity is explicitly stored within the dual graph (the so-called Delaunay triangulation). So, a certain degree of "what-if" analysis is possible when points are updated using ordinary Voronoi diagrams. However, the ordinary Voronoi diagrams are informative and meaningful only when points have identical weight (relevance, interest or growth rate) or only when the nearest neighbour is the only relation of concern.

Indeed, a large number of domains demand "what-if" analysis of more relations. Often, requiring (1) the k-th nearest neighbour (for example, the k-th nearest hospital in case k-1 nearest hospitals are closed or fully occupied), (2) the order-k nearest neighbour (the k nearest customers for business marketing), (3) the ordered order-k nearest neighbour (the ordered k nearest police stations in case emergency occurs), (4) the farthest neighbour (the farthest area from the pollutant) and (5) points having different weights (shopping centres having different facilities result in different catchment areas). All these five additional relations are modelled by generalised Voronoi diagrams: (1) k-th nearest-point Voronoi diagram, (2) order-k Voronoi diagram, (3) ordered order-k Voronoi diagram, (4) farthest Voronoi diagram and (5) weighted Voronoi diagram, respectively. In this demonstration, we present a GUI environment for "what-if" analysis when points have all the different meanings (distance concepts and weights) just mentioned.

The implemented application utilises our innovative common data structure, which supports jointly the ordinary Voronoi diagram and the five generalisations. This data structure holds spatial adjacency information with respect to generalised Voronoi vertices. That is, it is possible to derive all generalised Voronoi diagrams from this single data structure without storing the variants explicitly. In addition, spatial proximity information is easily retrieved, including generalised Voronoi regions and neighbours. Further, we demonstrate the ease by which our application facilitates compare and contrast amongst all the Voronoi diagrams within a common data set. Alternation from one diagram to another is also easily performed. In summary, our product enables users to effectively construct and interact with much more comprehensive "what-if" scenarios that could involve applications analysing complex cost functions or involve risk factors.

Download the application: voronoi.exe