A Voronoi diagram is a partition of a 2D plane into regions based on a set of points. Each region contains points that are closer to a particular point in the set than any other point. The diagram can be represented by a graph of boundaries, with vertices where multiple segments meet and edges connecting these vertices. The Delaunay triangulation is a related concept, where a Voronoi vertex is a Delaunay face and a Delaunay vertex is a Voronoi region. There are various algorithms to compute the Voronoi diagram or Delaunay triangulation, each with their own advantages and disadvantages. Fortune’s Algorithm is one approach that achieves a deterministic O(nlogn) time complexity, but uses floating points which can introduce precision errors.
https://codeforces.com/blog/entry/85638