Let M be the generator matrix of a $N\times N$ lattice, and $\tilde{N}$ the set of Voronoi relevant vectors. The Voronoi cell for the origin can be written as $\text{Vor}\_{\bf 0}(M)=\left\{{\bf x}: |{\bf x}|\leq|{\bf x-c}|\text{ for } \forall {\bf c}\in \tilde{N}\right\}$. My question is given $\tilde{N}$, how to find the closest lattice vector for a given point ${\bf x}\in R^N$? Equivalently, given $\tilde{N}$, how to translate the given point ${\bf x}$ back to $\text{Vor}\_{\bf 0}$?


If $\tilde{N}$ is not given, the closest point can be found with the algorithm introduced [here](https://publications.lib.chalmers.se/records/fulltext/14990/local_14990.pdf), and the same algorithm can be modified to find $\tilde{N}$. The motivation for my question is that I would like to find the closest points for a large number of ${\bf x}$'s, for the same lattice. Running the closest point search algorithm is very expensive, hence I am hoping to use relevant vectors to find the closest points.


This is my attempt to translate a given point ${\bf x}$ back to $\text{Vor}\_{\bf 0}$ given the relevant vectors $\tilde{N}$



```
for c in $\tilde{N}$
    overlap = x^T * c/norm(c)^2 
    if abs(overlap) > 1/2
        x = x - round(overlap) * c
    end
end

```

which seems working for 2D lattices, but not for 3D lattices. Hence I am not sure if the algorithm is correct, or if it is possible to do that for general lattices.



How to find the closest point given the Voronoi relevant vectors?
I believe state of the art for this is [Short Paths on the Voronoi Graph and Closest Vector
Problem with Preprocessing](https://arxiv.org/abs/1412.6168) by Bonifas and Dadush.
For instance, see the following quote from the abstract



> 
> Our main technical contribution is a randomized procedure that given the Voronoi relevant vectors of a lattice - the lattice vectors inducing facets of the Voronoi cell - as preprocessing and any "close enough" lattice point to the target, computes a path to a closest lattice vector of expected polynomial size. This improves on the $\tilde{O}(4^n)$ path length given by the MV algorithm. Furthermore, as in MV, each edge of the path can be computed using a single iteration over the Voronoi relevant vectors.
> 
> 
> 


This is to say that Bonifas+Dadush should imply a (randomized) algorithm of complexity $O(\mathsf{poly}(N)|\tilde{N}|)$ (as a side note, using $N$ for a dimension and $\tilde{N}$ for a set is perhaps not the best choice of notation).
Note that this may not mean *efficient*, as $|\tilde{N}|$ can grow exponentially in $N$.
But, if you have a lattice for which you know that $|\tilde{N}|$ is small, it should efficiently solve your problem.


Note that one can often solve CVP efficiently even in lattices that have exponentially many Voronoi relevant vectors.
This is true if they have small *extension complexity*, see [Lifts for Voronoi Cells of Lattices](https://arxiv.org/abs/2106.04432) by Schymura, Seidel, and Weltge.


It's also worth mentioning that there have been improvements for finding $\tilde{N}$.
In particular, see [A Deterministic Single Exponential Time Algorithm for Most Lattice Problems](http://cse.ucsd.edu/sites/cse/files/cse/assets/research/theory/MicciancioVoulgaris_2010_stoc.pdf) by Micciancio+Voulgaris.


