Introduction: What is a Voronoi Diagram?

2-Site Voronoi Diagrams

The standard Voronoi diagram of a set of n given points (called sites) is a subdivision of the plane into n regions, one associated with each site. Each site's region consists of all points in the plane closer to it than to any of the other sites. One application that frequently occurs is what Knuth called the "post office" problem. Given a letter to be delivered, the nearest post office to the sender can be found by identifying the sender's location in the Voronoi diagram of the post office sites. This is called a "locus approach" to solving the problem-points in the plane are broken into sets by the answer to a query (in this case, "Which post office is nearest?"). All points that give the same answer are in the same set. Answering queries is reduced to planar point location once the nearest-neighbor diagram is computed. When the furthest site is sought for every point in the plane, we obtain the furthest-neighbor Voronoi diagram.

The Voronoi diagram has been rediscovered many times in dozens of fields of study including crystallography, geography, metrology, and biology, as well as mathematics and computer science. A comprehensive review of the various variations of Voronoi diagrams and of the hundreds of applications of them is given by Okabe et al. [1].

In particular, there have been a number of studies of variants of the Voronoi diagrams based on non-Euclidean distance functions and on sites that are line segments, circles, polygons, and other shapes more complicated than points. Another studied variant is the kth-order Voronoi diagram. Here the plane is broken into regions where all points in a given region have the same k sites as their k nearest neighbors. However, even in this case the distance measure is based only on the pairwise distance. The regular (1-site) nearest-neighbor Voronoi diagram (with respect to the Euclidean distance function) can be viewed as the result of blowing circles around each point, where each point in the plane belongs to the region of the site whose circle sweeps it first. (Similarly, the furthest-neighbor diagram is constructed by considering, for each point in the plane, the last circle that sweeps it.) Note that: 1. All the circles start to grow at the same "time" t=0 (representing the zero distance from the sites); and 2. All the circles grow in the same speed. 2-site Voronoi diagrams (a notion first presented in [2]) are the results of blowing some family of shapes around each pair of sites. Each 2-site distance function is modeled by a different blown shape, and has a different setting of the initial times and growing rates of the respective shapes.

It is well known that the 1-site nearest- (resp., furthest-) neighbor Voronoi diagram is the xy-projection of the lower (resp., upper) envelope of the xy-monotone surfaces modeling the functions that measure the distance from each site. For every point (x,y) in the plane, the z coordinate of the respective Voronoi surface that corresponds to the site p is the two-dimensional distance from (x,y) to p. For the Euclidean distance function all the surfaces are copies of the same cone whose apex is translated to the sites. For 2-site distance functions, each pair of sites p,q is associated with a surface, where for every point (x,y,z) on the surface, the value z is the 2-site distance from (x,y) to the pair p,q. For each 2-site distance function we describe the associated family of Voronoi surfaces, the xy-projection of whose envelopes form the respective Voronoi diagrams.

Goal: 1-point & 2-point Site Voronoi Diagrams

s project gives an easy interface for creating and editing Voronoi Diagrams. The user can create diagrams of 1-point sites or 2-point sites. In addition, the user can edit the sites and the chosen distance function. The application comes with 14 built-in distance functions.

In addition to the expected interface for the creation and editing of the diagrams, our application offers the unique feature of allowing the user to create additional distance functions. This is done within the application and so the functions are compiled on-the-fly and can be used immediately.

All the data can be saved and loaded from files. Images of the diagram and of its legend can also be saved to files.

General Functionality

Diagrams

A Voronoi Diagram can be created and edited later. A diagram holds the following data: