I am looking for a package or an algorithm (which I am happy to code into a package and make it available) that expresses a coordinate inside a simplex as a convex combination “near” of points with integer coordinates.

Formally, for a given integer K \in \mathbb{N}, consider the simplex

defined by the sum of coordinates being \le K, and the points with integer coordinates

For an z \in S, I am looking for vertices v_i \in I, i = 0, \dots, M and weights \sum_{i = 0}^M \alpha_i = 1 such that

Ideally the v_i should be “near” z, but not necessarily the nearest if that’s difficult.

The problem is very easy for M = 2, but the naive algorithms I came up with fail for M = 3 — 2D is very easy to partition with self-similar simplexes like this:

But, importantly, for this algorithm the simplexes formed by the v_i for each z do not have to form a partition of S.

Here is some test code I would like to pass, if anyone wants to provide concrete code:

```
using LinearAlgebra, Test
f(z, K) = IMPLEMENTATION # returns a vector of vs and αs
ϵ = 1e-8 # just picked some arbitrary tolerance
for _ in 1:100
M = rand(3:5)
K = rand(2:10)
z = normalize(rand(M), 1) .* K
vs, αs = f(z, K)
ẑ = mapreduce((v, α) -> v .* α, (v1, v2) -> v1 .+ v2, vs, αs)
@test ẑ ≈ z atol = ϵ
@test sum(αs) ≈ 1 atol = ϵ
@test all(αs .≥ 0)
for v in vs
@test eltype(v) == Int # or all v are integers, can be stored as floats
@test all(v .≥ 0)
@test sum(v) ≤ K
end
end
```

But, again, I appreciate any kind of suggestions.