Can Voronoi diagrams of lattices be made disjoint?

74 Views Asked by At

Typically, given a full-rank lattice $\Lambda\subset\mathbb{R}^d$ the Voronoi cell centered at the origin is $$V_0:=\{x\in\mathbb{R}^d:|x|\leq |x-\lambda| \;\forall \lambda\in\Lambda\}.$$ Any such lattice tiles $\mathbb{R}^d$ by translations of $\Lambda$, i.e., $$\mathbb{R}^d = \bigcup_{\lambda\in\Lambda}V_0+\lambda =: \bigcup_{\lambda\in\Lambda}V_\lambda.$$ Clearly, nearby Voronoi regions can overlap on a face (facet of the boundary), but these are Lebesgue measure 0 sets.

My question is: Can we always redefine $V_0$ (or possibly all $V_\lambda$) in such a way that they are all pairwise disjoint, so that $$\mathbb{R}^d = \bigsqcup_{\lambda\in\Lambda}V_\lambda?$$

I can convince myself that in $\mathbb{R}^2$, lattices with Voronoi regions that are regular polygons should work this way (e.g., for the square take $V_0 = [0,1)^2$ and for the hexagon take three sides to be closed and the other three to be open, but exclude the endpoint of the two closed edges on the outside). The cube in $\mathbb{R}^3$ works similar to the square I think by using $V_0=[0,1)^3$.

1

There are 1 best solutions below

1
On BEST ANSWER

The answer to your question (as clarified in the comments) is positive. First, a definition:

Definition. Let $C\subset {\mathbb R}^n$ be a convex polyhedron (it does not have to be bounded). Then the relative interior of $C$, denoted ${C}^\circ$, is the interior of $C$ in the affine span of $C$. (The affine span is the smallest affine subspace of $\mathbb R^n$ containing the subset $C$.) Concretely, one defines ${C}^\circ$ as follows: Represent $C$ by a minimal system of linear equations and inequalities. (I.e. a system which has the least (total) number of equations and inequalities.) Replace all inequalities in this system by strict inequalities. The solution set of the resulting system is ${C}^\circ$.

Definition. Suppose that $C$ is a convex polyhedron in $\mathbb R^n$ and $F$ is a face of $C$. Then $F^\circ$ is called an open face of $C$.

Now, suppose that $V_0$ is the Voronoi cell as in your question. For every open $k$-dimensional face $F$ of $V_0$, $k=0,...,d$, we will do the following. List all the open faces of $V_0$ which have the form $\lambda+ F$ for $\lambda\in \Lambda$, let's call this list $L_F$. For each $F$ keep it as an open face of $V_0$ but remove from $V_0$ all the other open faces in the list $L_F$. Call the result $V_0'$. It is a nice exercise to check the following:

  1. $\bigcup_{\lambda\in \Lambda} (\lambda + V_0')= {\mathbb R}^d$.

  2. For any two distinct elements $\lambda_1, \lambda_2\in \Lambda$, $$ \lambda_1 + V_0'\cap \lambda_2 + V_0'=\emptyset. $$ (In other words, $V_0'$ is a strict fundamental domain of the lattice $\Lambda$.) This is what you have asked for.

Note: For this to work, you do not need $\Lambda$ to be a (full rank) lattice, it suffices to have a discrete subgroup of ${\mathbb R}^d$. Aside: lattices are usually required to be full rank, at least in my area of math. Also, there is nothing special here about the Voronoi construction, any tiling of $\mathbb R^d$ by convex fundamental polyhedra of $\Lambda$ would work.