Not that I know of, but it should be easy enough to set up for your self. Look at "Mean values over the space of lattices" by C. A. Rogers. You can take the generating vectors $(1/L^{1/(n-1)}, 0, 0, \ldots, a_1)$, $(0, 1/L^{1/(n-1)}, 0, \ldots, a_2)$, ..., $(0, \ldots, 1/L^{1/(n-1)}, a_{n-1})$, $(0, \ldots, 0, L)$ where $a_i$ are integers varying from 0 to L-1, and let L be larger and larger until you encounter a satisfactory lattice.

So an algorithm that would "theoretically enable one to write down generating vectors of such a lattice" is to discretize the space of lattices of determinant 1 and check each lattice. At a fine enough scale you will get a lattice with packing radius $>\rho$. You might ask for a bound on the discretization level required, but since this algorithm isn't practical anyway, I'm not sure if anyone has bothered to calculate such a bound.

I think the main idea is that when $\Lambda$ chosen randomly from the Siegel measure on lattice of determinant 1, and $\rho$ is such that $V_n\rho^n=\zeta(n)/2^{n-1}$, then the mean number of primitive lattice points (i. e. counting all points that lie on the same line through the origin as only one point) that fall in the ball of radius $2\rho$ is going to be 1. Since the number is obsiously not constant, that means there is a lattice where the number is zero.

I don't know if it's a standard name, but to me it seems natural to call such a point a "vertex".

You can even achieve this with convex solids, as noted to me by Douglas Zare in this comment: mathoverflow.net/questions/97933/touching-tetrahedra-graphs/‌​…

I think I'm missing something in your question. Can't you just put a regular k^n-gon K inside the n-cube and let f(x) be the nearest point in K to x?

@MattF. I asked Mathematica for the chromatic number of the graph whose vertices are $\{0,\tfrac18,\tfrac12,\tfrac78,1\}^2$ and two vertices share an edge if their distance is at least $\sqrt{65/64}$. Mathmetica claims the chromatic number is 4, so you seem to be correct in your conjecture.

I think this type of problem usually goes under the name (vector) quantization. There are some well established preprocessing approaches, e.g., k-d trees. Since nearest-neighbor models are standard examples in machine learning, you can find lots of useful explainers online (I found some by googling "nearest neighbor quantization k-d trees").

One $1\times\tfrac18$ and two $\tfrac78\times\tfrac12$ rectangles give a somewhat smaller diameter ($\sqrt{65/64}\approx1.008$).

conv(P) has nonempty interior iff the matrix [p1-p0, p2-p0,...pm-p0] is full rank