Approximating order-k Voronoi diagrams using clusters of sampled points

The Voronoi diagram is a versatile space partitioning structure finding applications in various areas of science and engineering.

Given a family S of sites, a Voronoi diagram (VD) partitions the plane into regions, one for each site in S. In the nearest VD, all points belonging to a region have the same nearest neighbor. Analogously, in the farthest VD, all points in a region have the same farthest neighbor. A generalized definition is that of the order-k Voronoi diagram,  where points belonging to a region have the same k nearest neighbors.

When the sites are not simple objects, and it is difficult to compute the exact nearest Voronoi diagram, a common approach is to sample the sites, compute the nearest VD of all points and keep the edges of the VD which are equidistant to different sites. The larger the sample of the sites the better the approximated diagram resembles the exact one. Unfortunately, this simple and efficient approach works only for the nearest VD and fails for any other order-k VD.

We propose a method of approximating order-k Voronoi diagrams by using Color Voronoi Diagrams (CVD), where each site is a cluster of points. More specifically, the concept is to sample a cluster of points from each site and to construct the order-k CVD, Such a diagram approximates the exact order-k diagram and can be accompanied by theoretical guarantees.

The goal of this project is to implement such construction algorithms and to experiment with different datasets. Work can then be extended to theoretical guarantees for the quality of the approximation or to the design of more efficient algorithms for special input sets.