The demonstrations below run in your browser. Click a demonstration to expand it:
k-covering radius of a two-dimensional lattice
The k-covering radius of a lattice L is the smallest r such that every point of the plane lies within distance r of at least k lattice points. For k = 1 this is the usual covering radius.
The simulation below draws the lattice generated by two vectors v1 (green) and v2 (purple). Drag the arrow tips to change the basis. The k-covering radius is estimated by sampling N random points of the fundamental parallelogram and taking the largest distance to the k-th nearest lattice point. The red circles of that radius, centered at the lattice points, then cover the plane k times.
Zone diagrams of points in the plane
The zone diagram of sites p1, …, pn (Asano, Matoušek and Tokuyama) is the unique family of regions R1, …, Rn in which Ri is the set of points at least as close to pi as to all the other regions. Unlike the Voronoi diagram it is defined implicitly, and already for two sites its boundary is a transcendental curve, the distance trisector.
Drag the sites, play the growth with the sweep level, and hover a boundary to see the chain of points it depends on. The slider α interpolates between the Voronoi diagram (α = 0) and the zone diagram (α = 1): each region competes with the others shrunk towards their sites by the factor α.