  We study the geometry and complexity of Voronoi cells of lattices with
respect to arbitrary norms. On the positive side, we show for strictly convex
and smooth norms that the geometry of Voronoi cells of lattices in any
dimension is similar to the Euclidean case, i.e., the Voronoi cells are defined
by the so-called Voronoi-relevant vectors and the facets of a Voronoi cell are
in one-to-one correspondence with these vectors. On the negative side, we show
that Voronoi cells are combinatorially much more complicated for arbitrary
strictly convex and smooth norms than in the Euclidean case. In particular, we
construct a family of three-dimensional lattices whose number of
Voronoi-relevant vectors with respect to the $\ell_3$-norm is unbounded. Our
result indicates, that the break through single exponential time algorithm of
Micciancio and Voulgaris for solving the shortest and closest vector problem in
the Euclidean norm cannot be extended to achieve deterministic single
exponential time algorithms for lattice problems with respect to arbitrary
$\ell_p$-norms. In fact, the algorithm of Micciancio and Voulgaris and its run
time analysis crucially depend on the fact that for the Euclidean norm the
number of Voronoi-relevant vectors is single exponential in the lattice
dimension.
