Navigation Menu

Skip to content

Instantly share code, notes, and snippets.

@serenity4
Created November 9, 2020 18:36
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save serenity4/7783951c517ecee5e40fb90768434c41 to your computer and use it in GitHub Desktop.
Save serenity4/7783951c517ecee5e40fb90768434c41 to your computer and use it in GitHub Desktop.
Statistics for the number of k-faces of a Voronoi triangulation
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")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment