Minkowski bisectors, Minkowski cells and lattice coverings

Abstract

The Dirichlet–Voronoi cell and parallelohedron are fundamental concepts in Geometry. In particular, they do play important roles in the study of ball packing and ball covering. However, to study packing and covering of general convex bodies, they are no longer so useful (see Theorem 0). By introducing Minkowski bisectors and Minkowski cells, this paper explores a new way to study the density $\theta ^*(C)$ of the thinnest lattice covering of $\mathbb {E}^n$ by a centrally symmetric convex body C. Several basic results (Theorems 2 and 4, Corollary 1) and unexpected geometric phenomena (Theorem 0, Example 1, Remark 4) about Minkowski bisectors, Minkowski cells and covering densities are discovered.

1 Introduction

Let $\mathbb {E}^n$ denote the n-dimensional Euclidean space with an orthonormal basis $\{ \mathbf{e}_1, \mathbf{e}_2, \ldots , \mathbf{e}_n\}$. For convenience we use small letters to denote real numbers, use small bold letters to denote points (or vectors) and use capital letters to denote sets of points in the space. In particular, let $\mathbf{o}$ denote the origin of $\mathbb {E}^n$, and let $B_n$ denote the n-dimensional unit ball $\{\mathbf{x}:\ \sum |x_i|^2\le 1\}$.

The bisector and the Dirichlet–Voronoi cell are two basic concepts in the Euclidean space (see [8] and [25, 26]). They have played very important roles in many geometric problems. For example, if $\Lambda$ is a lattice in $\mathbb {E}^n$, let r be the maximal number such that $rB_n+\Lambda$ is a packing in $\mathbb {E}^n$, let $r^{\prime }$ be the minimal number such that $r^{\prime }B_n+\Lambda$ is a covering of $\mathbb {E}^n$, and let D denote the Dirichlet–Voronoi cell determined by $\Lambda$ with respect to the Euclidean metric and centered at $\mathbf{o}$, then we have

$$\begin{aligned} rB_n\subset D\subset r^{\prime }B_n \end{aligned}$$

and $D+\Lambda$ is a lattice tiling of $\mathbb {E}^n$. Therefore, the Dirichlet–Voronoi cell does provide a basic tool for investigating both ball packing and ball covering. For the basic knowledge about the bisector and the Dirichlet–Voronoi cell we refer to [6, 9, 10] and [17].

Let K denote an n-dimensional convex body and let C denote a centrally symmetric one centered at the origin of $\mathbb {E}^n$. In particular, let P denote an n-dimensional parallelohedron, the polytope which can form a lattice tiling in $\mathbb {E}^n$. In 1885, Fedorov [13] discovered that, in $\mathbb {E}^2$ a parallelohedron is either a parallelogram or a centrally symmetric hexagon; in $\mathbb {E}^3$ a parallelohedron can be and only can be a parallelotope, a hexagonal prism, a rhombic dodecahedron, an elongated octahedron, or a truncated octahedron. In 1929, Delone [5] proved that any n-dimensional parallelohedron is the affine image of a Dirichlet–Voronoi cell of a suitable lattice when $n\le 4$.

Let $\theta ^*(K)$ denote the density of the thinnest lattice covering of $\mathbb {E}^n$ by K. It is well-known (see [12] or [22]) that, if $K+\Lambda$ is a lattice covering of $\mathbb {E}^2$, then K contains a centrally symmetric hexagon H such that $H+\Lambda$ is a tiling in $\mathbb {E}^2$. Of course, the similar statement is true for the ball in any dimensions. In these cases it provides a practical way to determine the values of $\theta ^*(K)$, if all the parallelohedral types in the corresponding dimension are known. Then a basic problem emerged: Whenever $K+\Lambda$ is a lattice covering of $\mathbb {E}^n$, $n\ge 3$, is there always a parallelohedron P satisfying both $P\subseteq K$ and $P+\Lambda$ is a tiling of $\mathbb {E}^n$? Unfortunately, as one will see in Sect. 2, this is not the case.

It is well-known that there is a one-to-one correspondence between Minkowski metrics and centrally symmetric convex bodies in $\mathbb {E}^n$ (see page 7 of [17]). Therefore, it is natural and necessary to study the corresponding objects of the bisector and the Dirichlet–Voronoi cell in any metric space.

It is easy to show that any bisector in the Euclidean space $\mathbb {E}^n$ is a hyperplane. So it divides the whole space nicely into two parts. However, for other metrics a bisector could be very strange (not homeomorphic to a hyperplane) and the corresponding cell could be very complicated. In particular, sometimes the cells of a lattice can no longer form a tiling of the space. Therefore, a direct generalization of the bisector and the Dirichlet–Voronoi cell to general metric spaces is not useful to the corresponding packing and covering problems. Nevertheless, there are many references on these topics (see [21] and [24]).

In this paper, for the purpose to study lattice packings and lattice covering of general centrally symmetric convex bodies, we introduce and study Minkowski bisectors and Minkowski cells with respect to a given Minkowski metric. Some basic results and unexpected phenomena such as Example 1, Theorems 0, 2 and 4, and Corollary 1 about Minkowski bisectors, Minkowski cells and covering densities are discovered.

2 A basic example

For convenience, we write $\alpha =\cos {\pi \over 3}$, $\beta =\sin {\pi \over 3}$ and take $\gamma$ to be a small positive number. We note that (1,0), $(\alpha , \beta )$, $(-\alpha , \beta )$, $(-1, 0)$, $(-\alpha , -\beta )$ and $(\alpha , -\beta )$ are the vertices of a regular hexagon. Let C denote a three-dimensional centrally symmetric convex polytope as shown in Fig. 1 with twelve vertices $\mathbf{v}_1=(1,0,1+\gamma )$, $\mathbf{v}_2=(\alpha , \beta , 1-\gamma )$, $\mathbf{v}_3=(-\alpha , \beta , 1+\gamma )$, $\mathbf{v}_4=(-1, 0 , 1-\gamma )$, $\mathbf{v}_5=(-\alpha , -\beta , 1+\gamma )$, $\mathbf{v}_6=(\alpha , -\beta , 1-\gamma )$, $\mathbf{v}_7=(1,0,-1+\gamma )$, $\mathbf{v}_8=(\alpha , \beta , -1-\gamma )$, $\mathbf{v}_9=(-\alpha , \beta , -1+\gamma )$, $\mathbf{v}_{10}=(-1, 0 , -1-\gamma )$, $\mathbf{v}_{11}=(-\alpha , -\beta , -1+\gamma )$ and $\mathbf{v}_{12}=(\alpha , -\beta , -1-\gamma )$, and let $\Lambda$ to be the lattice with a basis $\mathbf{a}_1=(1+\alpha , \beta , 0)$, $\mathbf{a}_2=(1+\alpha , -\beta , 0)$ and $\mathbf{a}_3=(0, 0, 2)$. In fact, C can be obtained from an hexagonal prism of height $2(1+\gamma )$ by cutting off six tetrahedra, all of them are congruent to each others.

Fig. 1

A basic example for covering

It can be easily verified that

$$\begin{aligned} \mathbf{v}_i=\mathbf{v}_{6+i}+\mathbf{a}_3 \end{aligned}$$

holds for all $i=1, 2, \ldots , 6$ and $C+\Lambda$ is a lattice covering of $\mathbb {E}^n$. If C contains a parallelohedron P such that $P+\Lambda$ is a tiling of $\mathbb {E}^3$, then P must contain all the twelve vertices $\mathbf{v}_1$, $\mathbf{v}_2$, $\ldots$, $\mathbf{v}_{12}$ of C and therefore $P=C$. However, C is not a parallelohedron. Thus, $C+\Lambda$ is a counterexample to the basic problem in $\mathbb {E}^3$.

If K is a counterexample in $\mathbb {E}^{n-1}$, defining $K^{\prime }$ to be the cylinder over K, one can easily show that $K^{\prime }$ will be a counterexample to the basic problem in $\mathbb {E}^n$. Therefore, we have proved the following result by explicit examples:

Theorem 0

Whenever $n\ge 3$, there is a lattice covering $C+\Lambda$ of $\mathbb {E}^n$ by a centrally symmetric convex body C such that C does not contain any parallelohedron P that $P+\Lambda$ is a tiling of $\mathbb {E}^n$.

3 The Minkowski bisectors

Let $\Vert \cdot \Vert _C$ denote a Minkowski metric determined by a centrally symmetric convex body C and let $\Vert \mathbf{x}, \mathbf{y}\Vert _C=\Vert \mathbf{y}-\mathbf{x}\Vert _C$ denote the Minkowski distance between two points $\mathbf{x}$ and $\mathbf{y}$ with respect to the metric. For two distinct points $\mathbf{p}$ and $\mathbf{q}$ in $\mathbb {E}^n$ we define

$$\begin{aligned} H(\mathbf{p}, \mathbf{q})=\left\{ \mathbf{y}\in \mathbb {E}^n:\ \langle \mathbf{y}, \mathbf{q}-\mathbf{p}\rangle =0\right\} \end{aligned}$$

and

$$\begin{aligned} L(\mathbf{p}, \mathbf{q}, \mathbf{x})=\left\{ \mathbf{x}+\lambda (\mathbf{q}-\mathbf{p}):\ \lambda \in \mathbb {R}\right\} , \end{aligned}$$

where $\mathbf{x}\in H(\mathbf{p}, \mathbf{q})$. In other words, $H(\mathbf{p}, \mathbf{q})$ is a hyperplane containing the origin and perpendicular to the vector $\mathbf{q}-\mathbf{p}$, and $L(\mathbf{p}, \mathbf{q}, \mathbf{x})$ is the straight line determined by the point $\mathbf{x}$ and the vector $\mathbf{q}-\mathbf{p}$. Then, for every $\mathbf{x}\in H(\mathbf{p}, \mathbf{q})$, we define

$$\begin{aligned} S(C, \mathbf{p}, \mathbf{q}, \mathbf{x})=\left\{ \mathbf{y}\in L(\mathbf{p}, \mathbf{q}, \mathbf{x}): \ \Vert \mathbf{p}, \mathbf{y}\Vert _C=\Vert \mathbf{q}, \mathbf{y}\Vert _C\right\} . \end{aligned}$$

Now let us introduce a basic result about $S(C, \mathbf{p}, \mathbf{q}, \mathbf{x})$ which is essential for the definition of the Minkowski bisectors.

Lemma 1

(Horváth [18]). For every $\mathbf{x}\in H(\mathbf{p}, \mathbf{q})$, the set $S(C, \mathbf{p}, \mathbf{q}, \mathbf{x})$ is either a single point or a closed segment.

Proof

Since C is a centrally symmetric convex body, both $f(\mathbf{y})=\Vert \mathbf{p}, \mathbf{y}\Vert _C$ and $g(\mathbf{y})=\Vert \mathbf{q}, \mathbf{y}\Vert _C$ are continuous functions of $\mathbf{y}$. On the other hand, when $\lambda$ is sufficiently large, we have

$$\begin{aligned} f(\mathbf{x}+\lambda (\mathbf{q}-\mathbf{p}))>g(\mathbf{x}+\lambda (\mathbf{q}-\mathbf{p})) \end{aligned}$$

and

$$\begin{aligned} f(\mathbf{x}-\lambda (\mathbf{q}-\mathbf{p}))<g(\mathbf{x}-\lambda (\mathbf{q}-\mathbf{p})). \end{aligned}$$

Thus it follows that $S(C, \mathbf{p}, \mathbf{q}, \mathbf{x})$ is nonempty. In addition, it can be easily deduced that $S(C, \mathbf{p}, \mathbf{q}, \mathbf{x})$ is always a compact set.

Now we show that if both $\mathbf{u}$ and $\mathbf{v}$ belong to $S(C, \mathbf{p}, \mathbf{q}, \mathbf{x})$ (see Fig. 2) then the whole segment $[\mathbf{u}, \mathbf{v}]$ belongs to $S(C, \mathbf{p}, \mathbf{q}, \mathbf{x})$.

Fig. 2

Structure of the bisectors

Assume that

$$\begin{aligned} \Vert \mathbf{p}-\mathbf{u}\Vert _C=\Vert \mathbf{q}-\mathbf{u}\Vert _C= & {} \alpha ,\\ \Vert \mathbf{p}-\mathbf{v}\Vert _C=\Vert \mathbf{q}-\mathbf{v}\Vert _C= & {} \beta \end{aligned}$$

and $\alpha <\beta$. It is easy to see that both $\mathbf{u}+\mathbf{p}-\mathbf{q}$ and $\mathbf{v}+\mathbf{p}-\mathbf{q}$ belong to $L(\mathbf{p}, \mathbf{q}, \mathbf{x})$, $\mathbf{u}$ is between $\mathbf{v}$ and $\mathbf{u}+\mathbf{p}-\mathbf{q}$ and therefore

$$\begin{aligned} \mathbf{u}-\mathbf{p}=\mu (\mathbf{v}-\mathbf{p})+(1-\mu )(\mathbf{u}+\mathbf{p}-\mathbf{q}-\mathbf{p}) \end{aligned}$$

holds for some $\mu$ with $0<\mu <1$. Thus we get

$$\begin{aligned} \alpha= & {} \Vert \mathbf{p}-\mathbf{u}\Vert _C\ge \mu \Vert \mathbf{p}-\mathbf{v}\Vert _C +(1-\mu )\Vert \mathbf{p}-\mathbf{u}\Vert _C\\\ge & {} \mu \beta +(1-\mu )\alpha =\alpha +\mu (\beta -\alpha )>\alpha . \end{aligned}$$

By this contradiction we can conclude that $\alpha =\beta$. Then it follows by convexity (since all $\mathbf{u}+\mathbf{p}-\mathbf{q}$, $\mathbf{v}+\mathbf{p}-\mathbf{q}$, $\mathbf{u}$ and $\mathbf{v}$ belong to the boundary of $\mathbf{p}+\alpha C$) that the whole segment $[\mathbf{u}+\mathbf{p}-\mathbf{q}, \mathbf{v}]$ belongs to the boundary of $\mathbf{p}+\alpha C$, the whole segment $[\mathbf{u}, \mathbf{v}+\mathbf{q}-\mathbf{p}]$ belongs to the boundary of $\mathbf{q}+\alpha C$, and therefore $[\mathbf{u}, \mathbf{v}]$ belongs to $S(C, \mathbf{p}, \mathbf{q}, \mathbf{x})$. $\Box$

Definition 1

Let $\mathbf{p}$ and $\mathbf{q}$ be fixed distinct points. For $\mathbf{x}\in H(\mathbf{p}, \mathbf{q})$ let $\overline{\mathbf{x}}$ denote the middle point of $S(C, \mathbf{p}, \mathbf{q}, \mathbf{x})$. Then we define

$$\begin{aligned} B(C, \mathbf{p}, \mathbf{q})=\left\{ \overline{\mathbf{x}}:\ \mathbf{x}\in H(\mathbf{p}, \mathbf{q})\right\} \end{aligned}$$

and call it a Minkowski bisector of $\mathbf{pq}$ with respect to $\Vert \cdot \Vert _C$.

Remark 1

In the literature like [4, 16, 18,19,20,21] and [27], the bisector was defined by

$$\begin{aligned} B^{\prime }(C, \mathbf{p}, \mathbf{q})=\left\{ S(C, \mathbf{p}, \mathbf{q}, \mathbf{x}):\ \mathbf{x} \in H(\mathbf{p}, \mathbf{q})\right\} . \end{aligned}$$

Clearly we have

$$\begin{aligned} B(C, \mathbf{p}, \mathbf{q})\subseteq B^{\prime }(C, \mathbf{p}, \mathbf{q}), \end{aligned}$$

where the equality holds if and only if the surface of C has no segment in the direction of $\mathbf{pq}$. As one will see from Sect. 4 that, for the purpose to study packing and covering, $B(C, \mathbf{p}, \mathbf{q})$ is more natural than $B^{\prime }(C, \mathbf{p}, \mathbf{q})$.

Let $f(\mathbf{x})$ be a map from $H(\mathbf{p}, \mathbf{q})$ to $B(C, \mathbf{p}, \mathbf{q})$ defined by $f(\mathbf{x})=\overline{\mathbf{x}}$. Clearly it is a one-to-one map. However it is less obvious if it is continuous in general. We note that in some references such as [18] and [21] our “continuous” is referred as “homeomorphic to a hyperplane”. In fact, as one can see from the following lemma and example, the situation is quite complicated.

Lemma 2

In $\mathbb {E}^2$, for any given metric $\Vert \cdot \Vert _C$ and given distinct points $\mathbf{p}$ and $\mathbf{q}$, the map $f(\mathbf{x})=\overline{\mathbf{x}}$ from $H(\mathbf{p}, \mathbf{q})$ to $B(C, \mathbf{p}, \mathbf{q})$ is continuous.

Proof

Without loss of generality, we assume that $\mathbf{p}=\mathbf{o}$ and $\mathbf{q}=\mathbf{e}_2$. Then the set $H(\mathbf{p}, \mathbf{q})$ is the x-axis. Let $R_1$ denote the set of points $\mathbf{x}\in H(\mathbf{p}, \mathbf{q})$ such that $S(C, \mathbf{p}, \mathbf{q}, \mathbf{x})$ is a single point and write $R_2=H(\mathbf{p}, \mathbf{q})\setminus R_1$.

By repeating partial argument of Lemma 1, it can be deduced that $R_1$ is closed and if $(x_1,0)\in R_2$, then $(x_2,0)\in R_2$ whenever $|x_2|\ge |x_1|$. In addition, if $x_0=\max \{ x: (x,0)\in R_1\}$, $\mathbf{x}_0=(x_0, 0)$ and $f(\mathbf{x}_0)=(x_0,y_0)$, then $f(\mathbf{x})$ (for $(x,0)\in R_2$ and $x>0$) is the middle point of $[\mathbf{g}_1,\mathbf{g}_2]$, where $\mathbf{g}_1=(x, {{y_0}\over {x_0}}x)$ and $\mathbf{g}_2=(x, 1+{{y_0-1}\over {x_0}}x)$, as shown in Fig. 3. In other words $f(\mathbf{x})$ is an half straight line for $x\ge x_0$. Similarly, one can deal with the case that $(x,0)\in R_2$ and $x\le -x_0$.

Then the continuity of $f(\mathbf{x})$ follows easily, by considering two cases $\mathbf{x}\in R_1$ and $\mathbf{x}\in R_2$. $\square$

Fig. 3

Structure of the Minkowski bisectors

Example 1

In $\mathbb {E}^3$ let us define

$$\begin{aligned} C=\mathrm{conv}\{ \mathbf{v}, S, -\mathbf{v}\}, \end{aligned}$$

where $S=\{ (x,y,0):\ x^2+y^2\le 1\}$ and $\mathbf{v}=(1,0,1)$. It is easy to see that C is a centrally symmetric convex body and its surface has only two vertical segments, they are $[\mathbf{e}_1, \mathbf{v}]$ and $[-\mathbf{e}_1, -\mathbf{v}]$. Take $\mathbf{p}=(0,0,0)$ and $\mathbf{q}=(0,0,1)$ and let $\mathbb {H}$ denote the set of all planes which containing both $\mathbf{p}$ and $\mathbf{q}$. By considering the intersections with planes $H\in \mathbb {H}$, one can deduce that the Minkowski bisector $B(C, \mathbf{p}, \mathbf{q})$ with respect to $\Vert \cdot \Vert _C$ consists of two parts L and M, where L is a straight line $\{ (x ,0,{1\over 2}(x+1)):\ x \in \mathbb {R}\}$ and M is a set between two planes $M_1=\{ (x,y,z):\ z=0\}$ and $M_2=\{ (x,y,z):\ z=1\}$, as shown in Fig. 4. Therefore it is easy to see that the map $f(\mathbf{x})=\overline{\mathbf{x}}$ is not continuous at the points (x, 0, 0) whenever $|x|>1$. By adding more edges similar to $[\mathbf{e}_1, \mathbf{v}]$, one can make the situation much more complicated.

Fig. 4

A Minkowski bisector which is not continuous

Let $\mathcal {C}$ denote the set of all n-dimensional centrally symmetric convex bodies centered at the origin $\mathbf{o}$ and let $\delta (\cdot , \cdot )$ denote the Hausdorff metric defined on $\mathcal {C}$. In other words,

$$\begin{aligned} \delta (C_1, C_2)=\min \{ \gamma :\ C_1\subseteq C_2+\gamma B_n;\ C_2\subseteq C_1+\gamma B_n\}. \end{aligned}$$

Let $\mathbf{p}$ and $\mathbf{q}$ be two fixed distinct points, let $C_0$ be a centrally symmetric convex body, and let $C_1$, $C_2$, $\ldots$ be a sequence of centrally symmetric convex bodies. It is natural to ask, would $B(C_i, \mathbf{p}, \mathbf{q})$ converges to $B(C_0, \mathbf{p}, \mathbf{q})$ if

$$\begin{aligned} \lim _{i\rightarrow \infty }\delta (C_i,C_0)=0\ \! ? \end{aligned}$$

Unfortunately, as one will see from the next example, the answer to this question is negative, even in the plane.

Example 2

In the plane we define

$$\begin{aligned} C_0=\{ (x,y):\ -1\le x\le 1;\ -1\le y\le 1\} \end{aligned}$$

and

$$\begin{aligned} C_i=\mathrm{conv}\left\{ \pm (1,1), \pm (1,0), \pm \left( 1-{1\over i}, -1\right) \right\} \end{aligned}$$

for $i=1, 2, \ldots .$ Then we have

$$\begin{aligned} \lim _{i\rightarrow \infty }\delta (C_i, C_0)=0. \end{aligned}$$

Let $\mathbf{p}=(0,0)$ and $\mathbf{q}=(0, 2)$, we have

$$\begin{aligned} B(C_0, \mathbf{p}, \mathbf{q})=\{ (x, 1):\ x\in \mathbb {R}\}. \end{aligned}$$

However, as shown by Fig. 5, the Minkowski bisector $B(C_i, \mathbf{p}, \mathbf{q})$ consists of points (x, y) satisfying

$$\begin{aligned} y=\left\{ \begin{array}{ll} {1\over 2}x+1, &{} \quad {{ if} \ |x|\ge 2,}\\ {i\over {i+1}}(x+2), &{} \quad {{ if}\ -2\le x\le {1\over i}-1,}\\ 1, &{} \quad {{ if}\ |x|\le 1-{1\over i},}\\ {i\over {i+1}}x+{2\over {i+1}}, &{}\quad {{ if} \ 1-{1\over i}\le x\le 2,} \end{array}\right. \end{aligned}$$

Therefore the sequence $B(C_i, \mathbf{p}, \mathbf{q})$ does not converge to $B(C_0, \mathbf{p}, \mathbf{q}).$

Fig. 5

Non-convergence of the Minkowski bisectors

If $B(C, \mathbf{p}, \mathbf{q})$ is a continuous surface, then it divides the whole space nicely into two half spaces. Unfortunately, as it was shown by Example 1, the Minkowski bisectors are not always continuous. Nevertheless, for many important metrics, the continuity can be guaranteed by the next lemma.

Lemma 3

If C is a centrally symmetric strictly convex body or a centrally symmetric polytope, for any pair of distinct points $\mathbf{p}$ and $\mathbf{q}$, the map $f(\mathbf{x})=\overline{\mathbf{x}}$ from $H(\mathbf{p},\mathbf{q})$ to $B(C, \mathbf{p}, \mathbf{q})$ is continuous.

Proof

First let us deal with the strictly convex case. Then, for any point $\mathbf{x}\in H(\mathbf{p}, \mathbf{q})$, $S(C, \mathbf{p}, \mathbf{q}, \mathbf{x})$ is a single point. If the map is not continuous at point $\mathbf{x}_0$, then one can deduce that $S(C, \mathbf{p}, \mathbf{q}, \mathbf{x}_0)$ is not a single point. The strictly convex case follows.

Now we consider the polytope case. Let P be an n-dimensional centrally symmetric convex polytope, let $P^{\prime }$ denote its projection on $H(\mathbf{p}, \mathbf{q})$, and let $\partial (P^{\prime })$ denote the relative boundary of $P^{\prime }$. Clearly $P^{\prime }$ is a $(n-1)$-dimensional centrally symmetric polytope and $\partial (P^{\prime })$ is a polytope complex of dimension less than or equal to $n-2$.

Let $\mathbf{v}$ be a point in $\partial (P^{\prime })$, let $\mathbf{v}^*$ denote the point $\mathbf{v}+\mu (\mathbf{q}-\mathbf{p})\in P$ with maximal $\mu$, let $\mathbf{v}^{\prime }$ denote the corresponding point with minimal $\mu$, and write

$$\begin{aligned} h(\mathbf{v})={{\Vert \mathbf{v}^*-\mathbf{v}^{\prime }\Vert }\over {\Vert \mathbf{q}-\mathbf{p}\Vert }}. \end{aligned}$$

Since P is a polytope, by convexity, it is easy to see that both $g_1(\mathbf{v})=\mathbf{v}^*$ and $g_2(\mathbf{v})=\mathbf{v}^{\prime }$ are continuous maps for $\mathbf{v}\in \partial (P^{\prime })$, and $h(\mathbf{v})$ is a continuous function for $\mathbf{v}\in \partial (P^{\prime })$.

Fig. 6

From a bisector to a Minkowski bisector

Let $Q(\mathbf{p}, \mathbf{q}, \mathbf{v})$ denote the two-dimensional hyperplane determined by $\mathbf{p}$, $\mathbf{q}$ and $\mathbf{v}$. By studying the intersections with $Q(\mathbf{p}, \mathbf{q}, \mathbf{v})$, it can be shown that $S(P, \mathbf{p}, \mathbf{q}, \alpha \mathbf{v})$ is a single point if and only if $\alpha \le 1/h(\mathbf{v})$ (when $h(\mathbf{v})=0$, $\alpha$ can be any number). For $\alpha \mathbf{v}\in H(\mathbf{p}, \mathbf{q})$, let $f_1(\alpha \mathbf{v})$ denote the point $\alpha \mathbf{v}+\mu (\mathbf{q}-\mathbf{p})$ in $S(P, \mathbf{p}, \mathbf{q}, \alpha \mathbf{v})$ with the maximal $\mu$ and let $f_2(\alpha \mathbf{v})$ denote the corresponding point in $S(P, \mathbf{p}, \mathbf{q}, \alpha \mathbf{v})$ with the minimal $\mu$. When $\alpha >1/h(\mathbf{v})$, illustrated by Fig. 6, it can be shown by similar triangles that

$$\begin{aligned} f_1(\alpha \mathbf{v})= & {} \alpha \mathbf{v}^*, \\ f_2(\alpha \mathbf{v})= & {} \alpha \mathbf{v}^*-(\alpha \ h(\mathbf{v})-1)(\mathbf{q}-\mathbf{p}) \end{aligned}$$

and

$$\begin{aligned} f(\alpha \mathbf{v})=\alpha \mathbf{v}^*- {1\over 2}(\alpha \ h(\mathbf{v})-1)(\mathbf{q}-\mathbf{p}). \end{aligned}$$

(1)

Let $H_1(\mathbf{p},\mathbf{q})$ denote the set of the points $\mathbf{x}\in H(\mathbf{p}, \mathbf{q})$ such that $S(P, \mathbf{p}, \mathbf{q}, \mathbf{x})$ is not a single point. It can be shown that $H_1(\mathbf{p},\mathbf{q})$ is an open set and therefore $H(\mathbf{p}, \mathbf{q})\setminus H_1(\mathbf{p}, \mathbf{q})$ is a closed set. By (1) it follows that $f(\mathbf{x})$ is continuous in $\overline{H_1(\mathbf{p}, \mathbf{q})}$. On the other hand $f(\mathbf{x})$ is continuous in $H(\mathbf{p}, \mathbf{q})\setminus H_1(\mathbf{p}, \mathbf{q})$. Therefore $f(\mathbf{x})$ is a continuous map from $H(\mathbf{p}, \mathbf{q})$ to $B(P, \mathbf{p}, \mathbf{q})$. The lemma is proved. $\square$

By the previous proof, it is easy to see that the Minkowski bisector $B(P, \mathbf{p}, \mathbf{q})$ consists of $(n-1)$-dimensional polytopes if the metric is defined by a polytope P. Let $\varphi (P, \mathbf{p}, \mathbf{q})$ denote the minimal number k such that the Minkowski bisector of $\mathbf{p}$ and $\mathbf{q}$ with respect to $\Vert \cdot \Vert _P$ can be divided into k polytopes of $(n-1)$-dimensional. We have the following results.

Theorem 1

If P is a centrally symmetric polygon with m vertices. Then, we have

$$\begin{aligned} \varphi (P, \mathbf{p}, \mathbf{q})\le m-1. \end{aligned}$$

Proof

For convenience, without loss of generality, we take $\mathbf{p}=(0,0)$ and $\mathbf{q}=(0,1)$. Let $\lambda$ change from 0 to infinity, it is easy to see that the boundaries of $\lambda P+\mathbf{p}$ and $\lambda P+\mathbf{q}$ intersect each other whenever $\lambda \ge \alpha$ for some $\alpha$.

Fig. 7

A Minkowski bisector of a polygon

For some $\beta >0$, assume that the boundaries of $\beta P+\mathbf{p}$ and $\beta P+\mathbf{q}$ meet at a vertex $\mathbf{v}_1$ of $\beta P+\mathbf{p}$ or $\beta P+\mathbf{q}$ (see Fig. 7), $\mathbf{v}_1\mathbf{v}_2$ is an edge of $\beta P+\mathbf{p}$, $\mathbf{v}_1\mathbf{v}_3$ is an edge of $\beta P+\mathbf{q}$. Let $M_2$ denote the line which is parallel to $\mathbf{v}_1\mathbf{v}_2$ and pass through $2\mathbf{v}_2$, let $M_3$ denote the line which is parallel to $\mathbf{v}_1\mathbf{v}_3$ and pass through $2(\mathbf{v}_3-\mathbf{q})+\mathbf{q}$, let $\mathbf{m}$ be the intersection of $M_2$ and $M_3$, let L denote the line passes $\mathbf{v}_1$ and $\mathbf{m}$, let $L_2$ denote the line determined by $\mathbf{p}$ and $\mathbf{v}_2$, and let $L_3$ denote the line determined by $\mathbf{q}$ and $\mathbf{v}_3$. Then $L_2$ intersects L at a point $\mathbf{u}_2$ and $L_3$ intersects L at a point $\mathbf{u}_3$. Let $\mathbf{u}$ denote the $\mathbf{u}_i$ which is closer to $\mathbf{v}_1$. By elementary geometry it is easy to see that the whole segment $[ \mathbf{u}, \mathbf{v}_1]$ belongs to $B(P, \mathbf{p}, \mathbf{q})$. In addition, for some $\gamma >0$, the boundaries of $\gamma P+\mathbf{p}$ and $\gamma P+\mathbf{q}$ meet at $\mathbf{u}$ and $\mathbf{u}$ is a vertex of either $\gamma P+\mathbf{p}$ or $\gamma P+\mathbf{q}$. By repeating this process and dealing with two cases with respect to if $\partial (C)$ contains a segment which is parallel to $\mathbf{p}{} \mathbf{q}$ or not, it can be shown that

$$\begin{aligned} \varphi (P, \mathbf{p}, \mathbf{q})\le m-1. \end{aligned}$$

The theorem is proved. $\square$

Remark 2

It is easy to see that

$$\begin{aligned} B(\lambda C, \mathbf{p}, \mathbf{q})=B(C, \mathbf{p}, \mathbf{q}) \end{aligned}$$

holds for all positive number $\lambda$. Thus, for a fixed polytope P, the number $\varphi (P, \mathbf{p}, \mathbf{q})$ is determined by the direction of $\mathbf{p}{} \mathbf{q}$. In fact, it follows by the proof of Theorem 1 that,

$$\begin{aligned} \varphi (P,\mathbf{p}, \mathbf{q})=m-1 \end{aligned}$$

holds for all $\mathbf{p}$ and $\mathbf{q}$, except for a finite number of directions $\mathbf{p}{} \mathbf{q}$.

In higher dimensions the situation is much more complicated. We have the following upper bound for $\varphi (P, \mathbf{p}, \mathbf{q})$.

Theorem 2

Let $n\ge 3$ be an integer and let P be an n-dimensional centrally symmetric polytope with m facets. Then

$$\begin{aligned} \varphi (P, \mathbf{p}, \mathbf{q})\le 1\over 4m^2+ {1\over {27}}m^3 \end{aligned}$$

holds for any pair of distinct points $\mathbf{p}$ and $\mathbf{q}$.

Proof

Let F denote a facet of P, let $\mathbf{n}(F)$ denote its outer unit normal, and let $\mathcal {F}$ denote the set of the m facets of P. Then we define

$$\begin{aligned} {\mathcal {F}}_{-}= & {} \{ F\in {\mathcal {F}}:\ \langle \mathbf{n}(F), \mathbf{q}-\mathbf{p}\rangle <0\},\\ {\mathcal {F}}_{0}= & {} \{ F\in {\mathcal {F}}:\ \langle \mathbf{n}(F), \mathbf{q}-\mathbf{p}\rangle =0\}\ \end{aligned}$$

and

$$\begin{aligned} {\mathcal {F}}_{+}=\{ F\in {\mathcal {F}}:\ \langle \mathbf{n}(F), \mathbf{q}-\mathbf{p}\rangle >0\}. \end{aligned}$$

It is easy to see, let |X| denote the number of the elements of X, that these three sets are pairwise disjoint and satisfying

$$\begin{aligned} | {\mathcal {F}}_{-}|=| {\mathcal {F}}_{+}|\le {1\over 2}m \end{aligned}$$

(2)

and

$$\begin{aligned} | {\mathcal {F}}_{-}|+ | {\mathcal {F}}_{0}|+ | {\mathcal {F}}_{+}|=m. \end{aligned}$$

(3)

Assume that $B(P,\mathbf{p}, \mathbf{q})$ can be divided into $\varphi (P, \mathbf{p}, \mathbf{q})$ polytopes $G_1$, $G_2$, $\ldots$, $G_{\varphi (P, \mathbf{p}, \mathbf{q})}$ of $(n-1)$-dimensional and write

$$\begin{aligned} {\mathcal {G}}=\{ G_i:\ i=1, 2, \ldots , \varphi (P, \mathbf{p}, \mathbf{q})\}. \end{aligned}$$

For each i let $\mathbf{w}_i$ be a relative interior point of $G_i$ such that there are a relative interior point $\mathbf{u}_i$ of a facet which belongs to either $\mathcal {F}_-$ or $\mathcal {F}_0$, a relative interior point $\mathbf{v}_i$ of a facet which belongs to either $\mathcal {F}_0$ or $\mathcal {F}_+$, and a positive number $\lambda _i$ satisfying

$$\begin{aligned} \mathbf{w}_i=\lambda _i\mathbf{u}_i+\mathbf{q}=\lambda _i\mathbf{v}_i+\mathbf{p}. \end{aligned}$$

(4)

If $\mathbf{u}_i\in F\in \mathcal {F}_0$, by looking at Fig. 6, it can be deduced that $\mathbf{v}_i\in F$.

Then $\mathcal {G}$ can be divided into two disjoint subsets

$$\begin{aligned} \mathcal {G}_1=\left\{ G_i:\ \mathbf{u}_i\in \bigcup _{F\in \mathcal {F}_-}F\right\} \end{aligned}$$

and

$$\begin{aligned} \mathcal {G}_2=\left\{ G_i:\ \mathbf{u}_i\in \bigcup _{F\in \mathcal {F}_0}F\right\} . \end{aligned}$$

Clearly we have

$$\begin{aligned} \varphi (P, \mathbf{p}, \mathbf{q})=|\mathcal {G}_1| + |\mathcal {G}_2|. \end{aligned}$$

(5)

Now we proceed to estimate $|\mathcal {G}_1|$ and $|\mathcal {G}_2|$, respectively.

If $\mathbf{u}_i$ and $\mathbf{u}_j$ belong to one facet $F^*$ in $\mathcal {F}_-$ and $\mathbf{v}_i$ and $\mathbf{v}_j$ belong to one facet $F^{\prime }$ in $\mathcal {F}_+$, then one can deduce that $\mathbf{w}_i$ and $\mathbf{w}_j$ should belong to the same $(n-1)$-dimensional polytope. In other words, the whole segment $[ \mathbf{w}_i, \mathbf{w}_j]$ belongs to $B(P, \mathbf{p}, \mathbf{q})$. To see this, when $0\le \theta \le 1$, writing $\lambda =\theta \lambda _i+(1-\theta )\lambda _j$ and $\theta ^{\prime }=\theta \lambda _i /\lambda$, we have

$$\begin{aligned} \theta \mathbf{w}_i+(1-\theta )\mathbf{w}_j= & {} \theta (\lambda _i\mathbf{u}_i+\mathbf{q}) +(1-\theta )(\lambda _j\mathbf{u}_j+\mathbf{q})\\= & {} \theta \lambda _i\mathbf{u}_i+(1-\theta )\lambda _j\mathbf{u}_j+\mathbf{q}\\= & {} \lambda (\theta ^{\prime }{} \mathbf{u}_i+(1-\theta ^{\prime })\mathbf{u}_j)+\mathbf{q} \end{aligned}$$

and

$$\begin{aligned} \theta \mathbf{w}_i+(1-\theta )\mathbf{w}_j= & {} \theta (\lambda _i\mathbf{v}_i+\mathbf{p}) +(1-\theta )(\lambda _j\mathbf{v}_j+\mathbf{p})\\= & {} \theta \lambda _i\mathbf{v}_i+(1-\theta )\lambda _j\mathbf{v}_j+\mathbf{p}\\= & {} \lambda (\theta ^{\prime }{} \mathbf{v}_i+(1-\theta ^{\prime })\mathbf{v}_j)+\mathbf{p}, \end{aligned}$$

where

$$\begin{aligned} \theta ^{\prime }{} \mathbf{u}_i+(1-\theta ^{\prime })\mathbf{u}_j\in F^*\quad \mathrm{and}\quad \theta ^{\prime }{} \mathbf{v}_i+(1-\theta ^{\prime })\mathbf{v}_j\in F^{\prime }. \end{aligned}$$

Therefore $|\mathcal {G}_1|$ is bounded from above by the number of distinct pairs of facets $\{ F^*, F^{\prime }\}$ such that $F^*\in \mathcal {F}_-$ and $F^{\prime }\in \mathcal {F}_+$. Then by (2) we get

$$\begin{aligned} | \mathcal {G}_1| \le |\mathcal {F}_-|\cdot |\mathcal {F}_+|\le {1\over 4}m^2. \end{aligned}$$

(6)

For $F\in \mathcal {F}_0$ we write

$$\begin{aligned} \mathcal {G}(F)=\{ G_i:\ \mathbf{u}_i\in F\}. \end{aligned}$$

Let $\mathcal {F}_+^{\prime }$ denote the set of the facets $F^{\prime }$ of P such that $\langle \mathbf{n}(F^{\prime }), \mathbf{q}-\mathbf{p}\rangle >0$ and $F\cap F^{\prime }$ is a $(n-2)$-dimensional polytope and let $\mathcal {F}_-^{\prime }$ denote the set of the facets $F^*$ of P such that $\langle \mathbf{n}(F^*), \mathbf{q}-\mathbf{p}\rangle <0$ and $F\cap F^*$ is a $(n-2)$-dimensional polytope. For $\mathbf{u}_i$, $\mathbf{v}_i$ and $\mathbf{w}_i$ defined by (4) , let $\mathbf{u}^+_i$ denote the point $\mathbf{u}_i+\lambda (\mathbf{q}-\mathbf{p})\in P$ with the maximal $\lambda$, and let $\mathbf{u}^-_i$ denote the point $\mathbf{u}_i+\lambda (\mathbf{q}-\mathbf{p})\in P$ with the minimal $\lambda$. Then, we have $\mathbf{u}_i^+=\mathbf{v}_i^+$ and $\mathbf{u}_i^-=\mathbf{v}_i^-$. If both $\mathbf{u}^+_i$ and $\mathbf{u}^+_j$ belong to $\mathrm{int}(F\cap F^{\prime })$ for a facet $F^{\prime }\in \mathcal {F}_+^{\prime }$ and both $\mathbf{v}^-_i$ and $\mathbf{v}^-_j$ belong to $\mathrm{int}(F\cap F^*)$ for a facet $F^*\in \mathcal {F}_-^{\prime }$, by an argument similar to the previous case it can be deduced that both $\mathbf{w}_i$ and $\mathbf{w}_j$ belong to one $(n-1)$-dimensional polytope in $B(P,\mathbf{p}, \mathbf{q})$. Therefore $|\mathcal {G}(F)|$ is bounded from above by the number of distinct pairs of facets $\{ F^{\prime }, F^*\}$ such that $F^{\prime }\in \mathcal {F}_+^{\prime }$ and $F^*\in \mathcal {F}_-^{\prime }$. Consequently, we get

$$\begin{aligned} |\mathcal {G}(F)|\le |\mathcal {F}_-^{\prime }|\cdot |\mathcal {F}_+^{\prime }|\le |\mathcal {F}_-|\cdot |\mathcal {F}_+| \end{aligned}$$

and, by (3 ),

$$\begin{aligned} |\mathcal {G}_2| \le |\mathcal {F}_0|\cdot |\mathcal {F}_-|\cdot |\mathcal {F}_+|\le {{1\over {27}}}m^3. \end{aligned}$$

(7)

As a conclusion of (5), (6) and (7) we get

$$\begin{aligned} \varphi (P, \mathbf{p}, \mathbf{q})\le {1\over 4}m^2+ {1\over {27}}m^3. \end{aligned}$$

The theorem is proved. $\square$

Remark 3

Although we can not give a proof, the upper bound in Theorem 2 seems much too large. It is easy to see that the direction $\mathbf{p}{} \mathbf{q}$ such that $\mathcal {F}_0\not =\emptyset$ is a zero measure set on $\partial (B_n)$. Therefore we have

$$\begin{aligned} \varphi (P, \mathbf{p}, \mathbf{q})\le {1\over 4}m^2, \end{aligned}$$

unless the direction $\mathbf{pq}$ belongs to a zero measure set of $\partial (B_n)$.

4 Minkowski cells and Lattice coverings

Let C be an n-dimensional centrally symmetric convex body, and let $\mathbf{p}$ and $\mathbf{q}$ be two distinct points in $\mathbb {E}^n$. We recall that $H(\mathbf{p}, \mathbf{q})$ is the hyperplane $\{ \mathbf{x}:\ \langle \mathbf{x}, \mathbf{q}-\mathbf{p}\rangle =0\}$ and $\overline{\mathbf{x}}$ is the point $\mathbf{x}+\lambda (\mathbf{q}-\mathbf{p})$ in $B(C, \mathbf{p}, \mathbf{q})$. For convenience, we define

$$\begin{aligned} D(C, \mathbf{p}, \mathbf{q})=\{\overline{\mathbf{x}}+\lambda (\mathbf{q}-\mathbf{p}):\ \mathbf{x}\in H(\mathbf{p}, \mathbf{q}),\ \lambda \le 0\}. \end{aligned}$$

In principle, the structure of $D(C,\mathbf{p},\mathbf{q})$ can be very complicated. Nevertheless, we have the following general result.

Lemma 4

The set $D(C,\mathbf{p},\mathbf{q})$ is a star set with $\mathbf{p}$ as its origin.

Proof

For convenience, we take $\mathbf{p}=\mathbf{o}$. Then we proceed to show that, if $\mathbf{u}\in D(C, \mathbf{p},\mathbf{q})$, then $\alpha \mathbf{u}\in D(C,\mathbf{p}, \mathbf{q})$ holds for all $\alpha$ with $0\le \alpha \le 1$.

Let $Q(\mathbf{p}, \mathbf{q}, \mathbf{u})$ denote the two-dimensional plane determined by $\mathbf{p}$, $\mathbf{q}$ and $\mathbf{u}$. We consider the intersection of $D(C, \mathbf{p}, \mathbf{q})$ with $Q(\mathbf{p}, \mathbf{q}, \mathbf{u})$. Clearly, $\mathbf{u}\in D(C, \mathbf{p},\mathbf{q})$ implies

$$\begin{aligned} \Vert \mathbf{p}, \mathbf{u}\Vert _C\le \Vert \mathbf{q}, \mathbf{u}\Vert _C. \end{aligned}$$

(8)

Fig. 8

A section of $D(C, \mathbf{p}, \mathbf{q})$ is star shape

On the contrary, if

$$\begin{aligned} \mathbf{v}=\alpha \mathbf{u}\not \in D(C,\mathbf{p},\mathbf{q}) \end{aligned}$$

holds for some $\alpha <1$, we proceed to deduce a contradiction. Assume that

$$\begin{aligned} \mathbf{v}=\mathbf{y}+\lambda (\mathbf{q}-\mathbf{p}) \end{aligned}$$

with suitable $\mathbf{y}\in H(\mathbf{p},\mathbf{q})$ and $\lambda \in \mathbb {R}.$ Then the point $\overline{\mathbf{y}}$ corresponding to $\mathbf{y}$ on the Minkowski bisector is below $\mathbf{v}$, as shown in Fig. 8. By Lemma 2, there is a suitable $\mathbf{w}$ between $\mathbf{p}$ and $\mathbf{v}$ such that $\mathbf{w}\in B(C,\mathbf{p},\mathbf{q})$. Therefore,

$$\begin{aligned} \mathbf{w}\in \partial (\lambda C+\mathbf{p})\cap \partial (\lambda C+\mathbf{q}) \end{aligned}$$

holds for some suitable $\lambda$. Then we have

$$\begin{aligned} \mathbf{w}+\mathbf{q}-\mathbf{p}\in \partial (\lambda C+\mathbf{q}). \end{aligned}$$

If the whole segment $[\mathbf{w}, \mathbf{w}+\mathbf{q}-\mathbf{p}]$ belongs to $\partial (\lambda C+\mathbf{q})$, then one can deduce that the whole segment $[\mathbf{w}, \mathbf{u}]$ belongs to $D(C,\mathbf{p}, \mathbf{q})$ and thus $\mathbf{v}\in D(C,\mathbf{p},\mathbf{q})$, which contradicts the assumption. If

$$\begin{aligned}{}[\mathbf{w}, \mathbf{w}+\mathbf{q}-\mathbf{p}]\not \subset \partial (\lambda C+\mathbf{q}), \end{aligned}$$

then by convexity it can be deduced that

$$\begin{aligned} \Vert \mathbf{q}, \mathbf{u}\Vert _C<{{\Vert \mathbf{q}, \mathbf{u}\Vert }\over {\Vert \mathbf{q}, \mathbf{w}^{\prime }\Vert }}\cdot \lambda ={{\Vert \mathbf{p}, \mathbf{u}\Vert }\over {\Vert \mathbf{p}, \mathbf{w}\Vert }}\cdot \lambda =\Vert \mathbf{p}, \mathbf{u}\Vert _C, \end{aligned}$$

which contradicts (8).

As a conclusion, $\alpha \mathbf{u}\in D(C,\mathbf{p},\mathbf{q})$ holds for all $0\le \alpha \le 1.$ Lemma 4 is proved. $\square$

Remark 4

For the C, $\mathbf{p}$ and $\mathbf{q}$ defined in Example 1, the region $D(C, \mathbf{p}, \mathbf{q})$ is not closed. However, when $B(C, \mathbf{p}, \mathbf{q})$ is continuous, the region $D(C, \mathbf{p}, \mathbf{q})$ is closed.

Definition 2

Let C be a centrally symmetric convex body, let $\Lambda$ be a lattice and define

$$\begin{aligned} M(C, \Lambda )=\bigcap _{\mathbf{v}\in \Lambda \setminus \{ \mathbf{o}\}}D(C, \mathbf{o}, \mathbf{v}). \end{aligned}$$

We call $M(C, \Lambda )$ a Minkowski cell of $\Lambda$ with respect to the metric $\Vert \cdot \Vert _C$.

Remark 5

For fixed C, $\mathbf{p}$ and $\mathbf{q}$, it can be verified that both

$$\begin{aligned} B(\lambda C, \mathbf{p}, \mathbf{q})=B(C, \mathbf{p}, \mathbf{q}) \end{aligned}$$

and

$$\begin{aligned} D(\lambda C, \mathbf{p}, \mathbf{q})=D(C, \mathbf{p}, \mathbf{q}) \end{aligned}$$

hold for all positive numbers $\lambda$. If $\Lambda$ is a lattice and $\tau$ is a non-singular linear transformation from $\mathbb {E}^n$ to $\mathbb {E}^n$. Then we have

$$\begin{aligned} B(\tau (C), \tau (\mathbf{p}), \tau (\mathbf{q}))= & {} \tau (B(C, \mathbf{p}, \mathbf{q})),\\ D(\tau (C), \tau (\mathbf{p}), \tau (\mathbf{q}))= & {} \tau (D(C, \mathbf{p}, \mathbf{q})) \end{aligned}$$

and

$$\begin{aligned} M(\tau (C), \tau (\Lambda ))=\tau (M(C, \Lambda )). \end{aligned}$$

Remark 6

By Lemma 4 it follows that the Minkowski cells are centrally symmetric star sets centered at the origin. For example, if $C=\{ (x, y):\ |x|\le 1/2,\ |y|\le 1/2\}$ and $\Lambda$ is a lattice with a basis $\mathbf{a}=(5/6, 1/6)$ and $\mathbf{b}=(-1/6, 5/6)$. Then $M(C,\Lambda )$ is the star domain illustrated in Fig. 9. In the Euclidean case, $C=B_n$, all Minkowski bisectors are hyperplanes, and all Minkowski cells are parallelohedra.

Fig. 9

A particular Minkowski cell

Lemma 5

Let C be an n-dimensional centrally symmetric convex body, let $\Lambda$ be an n-dimensional lattice, and let $\gamma$ denote the smallest positive number such that $\gamma C+\Lambda$ is a covering of $\mathbb {E}^n$. Then

$$\begin{aligned} M(C,\Lambda )\subseteq \gamma C. \end{aligned}$$

Proof

If, on the contrary, there is a point $\mathbf{x}\in M(C, \Lambda )$ such that $\Vert \mathbf{o}, \mathbf{x}\Vert _C>\gamma .$ Since $\gamma C+\Lambda =\mathbb {E}^n$, there is a lattice point $\mathbf{v}\in \Lambda$ such that $\Vert \mathbf{v}, \mathbf{x}\Vert _C\le \gamma .$ Thus, we have

$$\begin{aligned} \mathbf{x}\not \in D(C, \mathbf{o}, \mathbf{v}) \end{aligned}$$

and hence

$$\begin{aligned} \mathbf{x}\not \in M(C, \Lambda ). \end{aligned}$$

The lemma is proved. $\square$

Theorem 3

Let C be a two-dimensional centrally symmetric convex domain and let $\Lambda$ be a two-dimensional lattice. Then the region $M(C, \Lambda )$ is a centrally symmetric star domain and $M(C,\Lambda )+\Lambda$ is a tiling.

Proof

First, by Definition 2, Lemma 4 and Remark 4, it follows that $M(C, \Lambda )$ is a centrally symmetric star domain. In other words, it is a centrally symmetric compact star set.

Now, we claim that

$$\begin{aligned} ( \mathrm{int} (M(C, \Lambda ))+\mathbf{v}_i)\cap (\mathrm{int} (M(C, \Lambda ))+\mathbf{v}_j)=\emptyset \end{aligned}$$

holds for all distinct lattice points $\mathbf{v}_i$ and $\mathbf{v}_j$.

If, on the contrary, without loss of generality there are a point $\mathbf{x}$, a positive number $\epsilon$ and a lattice point $\mathbf{v}$ such that

$$\begin{aligned} \epsilon C+\mathbf{x}\subseteq \mathrm{int} \left( M(C, \Lambda )\right) \cap \left( \mathrm{int} \left( M(C, \Lambda )\right) +\mathbf{v}\right) . \end{aligned}$$

(9)

Then, we observe the Minkowski bisector $B(C, \mathbf{o}, \mathbf{v})$. If $\mathbf{x}\in B(C, \mathbf{o}, \mathbf{v})$, then we have

$$\begin{aligned} \mathbf{x}+\epsilon \overline{\mathbf{v}}\not \in D(C, \mathbf{o}, \mathbf{v}) \end{aligned}$$

and

$$\begin{aligned} \mathbf{x}+\epsilon \overline{\mathbf{v}}\not \in M(C, \Lambda ), \end{aligned}$$

which contradicts to (9), where $\overline{\mathbf{v}}$ is the boundary point of C in the direction of $\mathbf{v}$ as defined in Sect. 2. If $\mathbf{x}\not \in B(C, \mathbf{o}, \mathbf{v})$, since $B(C, \mathbf{o}, \mathbf{v})$ divides $\mathbb {E}^2$ into two separated parts which contains $\mathrm{int}(M(C, \Lambda ))$ and $\mathrm{int}(M(C, \Lambda ))+\mathbf{v}$, respectively. Therefore, $\epsilon C+\mathbf{x}$ can’t belong to both $\mathrm{int}(M(C, \Lambda ))$ and $\mathrm{int}(M(C, \Lambda ))+\mathbf{v}$ simultaneously when $\epsilon$ is sufficiently small, which contradicts to (9) as well.

Next, we claim that for every point $\mathbf{x}\in \mathbb {E}^2$ there is a lattice point $\mathbf{v}$ such that

$$\begin{aligned} \mathbf{x}\in M(C, \Lambda )+\mathbf{v}. \end{aligned}$$

(10)

Without loss of generality, since $\Lambda$ is periodic, we assume that $\mathbf{x}\in \gamma C$. Clearly, we have

$$\begin{aligned} \gamma C\subseteq D(C, \mathbf{o}, \mathbf{q}) \end{aligned}$$

whenever $\Vert \mathbf{o}, \mathbf{q}\Vert _C>2\gamma .$ Therefore, there are at most $|2\gamma C\cap \Lambda |$ Minkowski bisectors which can effect $M(C, \Lambda )$. Consequently, we assume further that

$$\begin{aligned} \mathbf{x}\in \mathrm{int}(\gamma C)\setminus \bigcup _{\mathbf{v}_i, \mathbf{v}_j\in 2\gamma C\cap \Lambda }B(C, \mathbf{v}_i, \mathbf{v}_j). \end{aligned}$$

Fig. 10

The structure of the equidistance set

If, for any positive $\epsilon$ there is a point $\mathbf{x}^{\prime }$ such that $\mathbf{x}^{\prime }\in \epsilon C+\mathbf{x}$ and

$$\begin{aligned} \Vert \mathbf{o}, \mathbf{x}^{\prime }\Vert _C< \Vert \mathbf{v}, \mathbf{x}^{\prime }\Vert _C \end{aligned}$$

holds for all $\mathbf{v}\in 2\gamma C\cap (\Lambda \setminus \{ \mathbf{o}\}).$ Then, since $M(C, \Lambda )$ is compact, we have $\mathbf{x}\in M(C, \Lambda )$. If, there are a positive number $\epsilon ^{\prime }$ and a subset W of $2\gamma C\cap \Lambda$ with $|W|\ge 2$ such that

$$\begin{aligned} \Vert \mathbf{x}^{\prime }, \mathbf{w}_i\Vert _C=\min \{ \Vert \mathbf{x}^{\prime }, \mathbf{v}\Vert _C :\ \mathbf{v}\in 2\gamma C\cap \Lambda \} \end{aligned}$$

holds for all $\mathbf{x}^{\prime }\in \epsilon ^{\prime }C+\mathbf{x}$ and $\mathbf{w}_i\in W$. Then, $W\subset \partial (\lambda C)+\mathbf{x}$ holds for some suitable positive number $\lambda$. By Fig. 10 it can be shown that, if $\mathbf{w}_i$ and $\mathbf{w}_j$ are two distinct points in W, then the whole segment $[\mathbf{w}_i, \mathbf{w}_j]$ belongs to $\partial (\lambda C)+\mathbf{x}$ and thus all the points of W are colinear.

Assume that $\mathbf{w}_1$, $\mathbf{w}_2$, $\ldots$, $\mathbf{w}_k$ are the points of W that successively on a line H, as shown in Fig. 10. Since $W\subset \Lambda$, we have

$$\begin{aligned} \mathbf{w}_{i+1}-\mathbf{w}_i=\mathbf{w}_2-\mathbf{w}_1. \end{aligned}$$

Let $\Lambda ^{\prime }$ denote the affine lattice generated by W in H. In other words,

$$\begin{aligned} \Lambda ^{\prime }= \left\{ \mathbf{w}_1+z (\mathbf{w}_2-\mathbf{w}_1):\ z\in \mathbb {Z} \right\} . \end{aligned}$$

Then, $M(C, \Lambda ^{\prime })+\Lambda ^{\prime }$ is a tiling of $\mathbb {E}^2$. Therefore, as illustrated by Fig. 11, there is a $\mathbf{w}_i\in W$ such that

$$\begin{aligned} \mathbf{x}\in M(C, \Lambda ^{\prime })+\mathbf{w}_i \end{aligned}$$

and consequently

$$\begin{aligned} \mathbf{x}\in M(C, \Lambda )+\mathbf{w}_i. \end{aligned}$$

As a conclusion, $M(C, \Lambda )+\Lambda$ is a tiling of $\mathbb {E}^2$. Theorem 3 is proved. $\square$

Fig. 11

Every point belongs to a Minkowski cell

Theorem 4

Let C be an n-dimensional centrally symmetric convex body, let $\Lambda$ be an n-dimensional lattice, and let $\gamma$ denote the smallest positive number such that $\gamma C+\Lambda$ is a covering of $\mathbb {E}^n$. If $\partial (C)$ has no segment in the directions of $\{\mathbf{v}: \mathbf{v}\in 2\gamma C\cap (\Lambda \setminus \{ \mathbf{o}\})\}$, then the region $M(C, \Lambda )$ is a centrally symmetric star body and $M(C,\Lambda )+\Lambda$ is a tiling.

This result can be proved just like the Euclidean case. Let $\delta ^*(C)$ denote the density of the densest lattice packing of C and let $\theta ^*(C)$ denote the density of the thinnest lattice covering of $\mathbb {E}^n$ by C. For more about packing and covering we refer to [1,2,3, 14, 15, 23] and [28]. Since a polytope has finite number of facets, it is easy to construct lattices avoiding directions parallel to its facets. Thus, Theorem 4 has the following corollary.

Corollary 1

Let P be an n-dimensional centrally symmetric polytope and let $\mathcal {M}$ denote the set of all Minkowski cells $M(P, \Lambda )$ contained in P. Then, we have

$$\begin{aligned} \theta ^*(P)=\inf _{M\in \mathcal {M}}{{\mathrm{vol}(P)}\over {\mathrm{vol}(M)}}. \end{aligned}$$

Remark 7

When $C=B_3$, there are only five types of Minkowski cells (see [10]). Therefore, one can determine the values of $\delta ^*(B_3)$ and $\theta ^*(B_3)$ by studying a unit ball inscribed in parallelohedra or parallelohedra inscribed in a unit ball. For other particular nontrivial centrally symmetric convex bodies, for example the octahedron, to enumerate their Minkowski cells seems challenging and interesting. For an algorithms approach we refer to [7].

It was proved by Ewald et al. [11] that the line segment directions on the surface of an n-dimensional convex body is a very small subset of $\partial (B_n)$. Therefore, Theorem 4 and Corollary 1 could be improved further. We end this article by two open problems as following.

Problem 1

Let P be a particular centrally symmetric convex polytope such as a regular 2m-gon, a regular octahedron or a cube. Enumerate the different types (geometric or combinatorial) of the Minkowski cells $M(P, \Lambda )$ for all lattices $\Lambda$.

Problem 2

Let C be an n-dimensional centrally symmetric convex body such that all its Minkowski bisectors are continuous. Is $M(C, \Lambda )+\Lambda$ always a tiling of $\mathbb {E}^n$ for all lattice $\Lambda$?