Voronoi relevant vectors VS shortest vector

58 Views Asked by At

Let $L$ be an $n$-dimensional lattice with its Voronoi cell $\mathcal{V}$ is then defined as the set $\{x\in \mathbb R^n:|x|\le |x-v|, \mbox{ for all }v\in L\}$. A vector $v$ is called a Voronoi relevant vector if the hyperplane $\{x:\in \mathbb R^n:\langle x,v \rangle=|v|^2/2\}$ has an intersection with an $(n-1)$-dimensional face of $\mathcal{V}$.

If we take an arbitrary point $\lambda \in L$ that is not Voronoi relevant, can we always find a Voronoi relevant vector $v$ such that $||v|| < ||\lambda||$?

enter image description here

1

There are 1 best solutions below

2
On

No. In your picture, take $\lambda = (3/4)v$.

Your choice of vocabulary is a little confusing. Among other things, when you use roman letters for vectors, I expect $\lambda$ to be a scalar.

Here is what I think you mean.

You have a Voronoi tessellation determined by a set $L$ of points one of which is the origin. The cell $S$ containing the origin has facets each of which is part of a hyperplane $H_v$ perpendicular to and bisecting some other vector $v \in L$. Those particular vertices $v$ are what you call "Voronoi relevant". They are the ones you have to look at to determine $S$.

Let $w$ be any nonzero vector. Then the ray $\alpha w$ meets the boundary of $S$ at some facet $H_v$ (perhaps more than one), Since $v/2$ is the point on $H_v$ nearest the origin, you know $$ | w | < |v/2| \iff w \in \text{ the interior of } S. $$

If $w \not\in S$ then $|w| > |v/2|$ but you cannot guarantee any inequality stronger than that.