Information Technology Reference
In-Depth Information
B
Fig. 13.10. A Barycentric Voronoi Diagram of nine sites in the plane. With the
inclusion of the barycentre we have a total of 10 sites. The barycentre is marked
with a 'B'.
Rather than explore general BVDs we turn our attention to a related
variant: the similarly named Co-circular Barycentric Voronoi Diagram
(CBVD), which is defined below and illustrated in Fig. 13.6.
Definition 2: A Co-circular Barycentric Voronoi Diagram (CBVD) is
a BVD in which the original sites (that is, excluding their barycentre) are
co-circular.
CBVDs form the foundation of our quality metric for NRVs. First,
however, we focus on some theoretical development and enumerate
properties of CBVDs.
In the case in which the DAs are located on the circumference of the
RadViz circle the Voronoi sites (DAs) are all co-circular. Such Co-circular
Voronoi Diagrams are of limited interest due to the empty circle property
[11] of the Delaunay Triangulation, which is a geometric dual to the
Voronoi Diagram. However, by adding the barycentre of the initial sites as
a site itself we have constructed the CBVD, which is an interesting variant
of the Voronoi diagram. While a Voronoi Diagram variant in which all
Voronoi regions are sited by their centroid [13] (Centroidal Voronoi
Diagrams) exists we are unaware of any previous work matching the
construction of our CBVDs. The closest we have seen to anything similar
to our CBVDs is in de Berg et al. [14]. Those authors show what appears
Search WWH ::




Custom Search