Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have several questions concerning the Delaunay triangulation of a high dimensional lattice. Given an $n$-dimensional lattice $L$ and its Delaunay triangulation (partition of $R^n$ into simplices such that the circumsphere of any simplex does not contain any lattice point).

  1. Does the center of a circumsphere of a Delaunay simplex have to be contained inside the simplex?
  2. Does a set of any $n$ independent vectors such that each vector coincides with a Delaunay edge form a basis of $L$?
  3. Is there a basis $B = \{b_1,b_2,\ldots , b_n\}$ of $L$ such that the $n$ dimensional parallelepiped $B[0,1)^n$ can be decomposed into Delaunay simplices?

Any partial answer for any question or pointing to future reading would be greatly appreciated.

share|improve this question

1 Answer 1

The answer to 2 and 1 is "No".

For (2), observe that a positive answer here would imply all Delaunay simplices to be unimodular (i.e., have volume equal to $1/n!$ times the volume of a fundamental parallelepiped). This holds for $n\le 4$ but starts to fail for $n\ge 5$. See, for example, my paper "Lattice Delone simplices with super-exponential volume" (arXiv, journal) and the references therein.

For (1) I can give an explicit counter-example in dimension three. Consider the lattice generated by $(1,a,a)$, $(a,1,a)$ and $(a,a,1)$, for a very small positive number $a$. When $a=0$ the Delaunay "triangulation" is not a triangulation, but the decomposition of $R^3$ into unit cubes. The effect of making $a\ne 0$ (but small) is that these cubes are refined into simplices, all of which have (by continuity) their center very close to $(1/2,1/2,1/2)$. But it turns out that one of these simplices has the origin and the three basis vectors as vertices, so the center of the circumsphere is outside of it.

(Well, to be precise, the Delaunay "triangulation" of MY lattice is still not a triangulation; in it the unit cube is decomposed into two tetrahedra and one octahedron. But perturbing the coordinates of the basis further, and generically, will produce a true Delaunay triangulation with the same properties).

I am not sure about question (3), but would expect a negative answer as well.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.