Statistics for the number of k-faces of a Voronoi triangulation

voronoi_stats.jl

using Plots

"""
Lower and upper bounds on the number of `k`-faces for a Voronoi diagram in `d`-dimensional space using `n` points.
"""
function n_faces_voronoi(k, d, n; return_mean=true)
    vals = if k == 0
      r = div(d + mod(d, 2), 2)
      if mod(d, 2) == 0
        n^r/factorial(r), 2 * n^r/factorial(r)
      else
        n^r/factorial(r) * 1/(r*exp(1)), n^r/factorial(r)
      end
    elseif k == d-1 && d > 3
      binomial(n, 2)
    elseif div(d, 2) ≤ k ≤ d
      binomial(n, d - k + 1)
    else
      NaN, NaN
    end
    vals isa Tuple && return_mean && return Int(floor(sum(vals)/2))
    Int(vals)
end

"""
Lower and upper bounds of the sum of all numbers of k-faces.
"""
function n_faces_voronoi(d, n)
    sum(n_faces_voronoi.(0:d-1, d, n))
end

p1 = plot(5:100, n_faces_voronoi.(0, 3, 5:100), title="Number of vertices in 3D", xlabel="Voronoi points", ylabel="Vertices")
p2 = plot(5:100, n_faces_voronoi.(1, 3, 5:100), title="Number of edges in 3D", xlabel="Voronoi points", ylabel="Edges")
p3 = plot(5:100, n_faces_voronoi.(2, 3, 5:100), title="Number of faces in 3D", xlabel="Voronoi points", ylabel="Faces")

p4 = plot(5:100, n_faces_voronoi.(3, 5:100))

savefig(p1, "voronoi_vertices")
savefig(p2, "voronoi_edges")
savefig(p3, "voronoi_faces")
savefig(p4, "voronoi_sum_faces")