What are Voronoi Diagrams?
Given a set of
n points (or sites), a Voronoi Tessellation is a subdivision of the space into
n cells (polygons), each cell corresponding to one site. These cells have the property that a point q lies in the cell corresponding to a site pi iff d(pi, q) < d(pj, q) for i distinct from j. The segments in a Voronoi Tessellation correspond to all points in the plane equidistant to the two nearest sites. Read more about them here.
Computing the Voronoi Polygons
There are various algorithms to construct Voronoi diagrams, the most common being Fortune’ Algorithm. Fortune’s Algorithm uses O(nlogn) time.
In this example, I have utilized an inbuilt method:
d3.geom.voronoi to compute the vertices of the polygons in the Voronoi diagram.
The clients of CVMFS (CERN Virtual Machine File System) would like to connect to mirror servers that are closer to them so as to reduce the latency in communication. To make decisions regarding which server is closest to a particular client, we are using Voronoi diagrams. So, if a client belongs to a cell C in the Voronoi diagram, it should be served by the server S corresponding to the cell C.
This is an effort to visualize the approximate partition of space.
So, here’s how the visualization looks:
A zoomed-in view of the part where most sites are clustered:
The complete code for this plot along with the libraries (d3.js) are available on this Github repository.