Information Technology Reference
In-Depth Information
method, introduced in the next section, utilizes the well-known Voronoi
diagram
[11] of the image space. Voronoi diagrams have had abundant
research into their theoretical aspects and their application to problems in
biology, chemistry, epidemiology, and many other fields. A
comprehensive survey of Voronoi diagrams has been done by
Aurenhammer
[12]. By defining a formal method of partitioning the image
space, we describe in Section IV a quality metric for any visualization that
relies on dimensional anchors. In this section we focus solely on
visualizations, such as RadViz, which fall into the general class of NRVs.
III. Voronoi Partitioning of Normalized Radial
Visualizations
As seen in the last section, when one looks at a RadViz image we have an
intuitive sense for inter- and intra- cluster distance. Cluster validation
indices such as the Davies-Bouldin and Dunn indices
[10] use Euclidean
distance this way and the method we introduce here also assumes
implicitly that Euclidean distance is meaningful. To formally describe a
Voronoi diagram: consider a set of
n
points
}
in the two
dimensional plane. We refer to these points as sites. The Voronoi region
()
i
P
{, , , }
n
pp
p
12
Vp
for point
p
consists of all the points at least as close to
p
as to
any other site:
d z
. For
n
points in the
two dimensional plane, the Voronoi diagram can be constructed in
(log)
Vp
(){ |
x p
x
| |
p
x
|
j i
}
i
i
j
On
n
time
[11]. Equivalently we may also express
Vp
as the
()
i
intersection of half-planes
Hp p
is the half-plane
which contains all the points closer to
Hp p
, where
(, )
i
(, )
i
j
j
p
than to
p
.
[11]. Fig.13.4 is a general example of a Voronoi
Vp
()
Hp p
(, )
i
i
j
i
j
diagram.
Search WWH ::
Custom Search