VORONOI DIAGRAM BASED DIMENSIONAL ANCHOR ASSESSMENT FOR RADIAL VISUALIZATIONS - Information Visualisation: Techniques, Usability and Evaluation - page 266

IV. Quantifying NRV Quality Using Voronoi Partitioning
of the Image Space

Given that points located around the barycentre are undesirable we can
form a ratio U where

(5)

U # data images in barycentre region
total # data images

The smaller this ratio the better we consider the visualization quality.
Further, we can consider regions sited by DAs to be desirable in that data
images in these regions are clearly under the majority influence of the DAs
in which they are closest. For each of these regions we can similarly form
a ratio of membership in any particular region to the total number of data
images. By summing the ratios from the desirable regions and subtracting
the ratio from the barycentre

§

d

# data images in region ·

(6)

¦

i

Q U 12 U

¨ ¸

total data images

© ¹

i 1

we obtain a value Q such that d d. We consider a 1 Q 1 Q to be a 1

“very informative” NRV and a Q to be an “uninformative” NRV. 1

That is, when Q all the data images lay in regions closest to the

dimensional anchors and the user is able to see the expressed strength of
certain dimensions. For

1

Q , we consider the NRV to be uninformative
since all the data would be located around the barycentre. Of course, it may
simply be the case that the data set lacks significant expression by any
particular dimension(s). Another possibility is that the pull of a very large
number of dimensions is muting the effects of a small number of
dimensions. Such ambiguity leads to our choosing the description of
“uninformative.”
We consider a

1

Q to be an “informative” NRV. In this case there
may still be features of the data set which remain hidden.
The time complexity of computing Q is O( d log d + n log n ). That is,
for n data records and d DAs ( d +1 sites since we include the barycentre B)
we have: a single computation of the Voronoi Diagram O( d log d ),
calculating U which is determining the inclusion in the BR of each of the n
records. The BR is a convex polygon and the point-in-polygon algorithm

0