# Delaunay Triangulation of Parallelepiped

Given $n$ linearly independent vectors $v_1, v_2, \ldots, v_n$ in $n$-dimensional space. Let $V$ be the set of $2^n$ points of the form $x_1 v_1 + x_2v_2 + \ldots + x_nv_n$, in which $x_i$ can be $0$ or $1$. $V$ is the set of vertices of an n-dimensional parallelepiped. Is there any way to find the Delaunay triangulation of $V$ using subexponential space with respect to $n$? I understand that the size of the output is big, and we can't store the whole output. But is there any way to output the Delaunay edges one by one without storing the previous result?

Testing whether a pair of points $p_i$ and $p_j$ are the endpoints of a Delaunay edge can be solved as a linear programming feasability problem: Lift each point to one higher dimension by making its last coordinate be the sum of squares of the other coordinates. Then look for a hyperplane passing through $p_i$ and $p_j$, such that all the other points are on one side of it. This can be represented in linear inequality constraints by seeking a vector $v$ and scalar $c$ such that the dot product of $v$ with each point is at least $c$, and is exactly $c$ in the case of $p_i$ and $p_j$.
• Thanks David. The idea of lifting point to one higher dimension is interesting. By the way, I have another question. Is it possible to find all Delaunay edges in $2^{O(n)}$ using subexponential space? – Jinx Nov 5 '13 at 3:17
• it's definitely in polynomial time and space with respect to the number of points. Here we have $2^n$ vertices given by $n$ linearly independent vectors, and I ask for an algorithm running in subexponential space in $n$. If it's possible to solve a linear programming of $2^n$ inequalities in $2^{o(n)}$ space then your algorithm will works. But then the running time will probably be bad, so I wonder if it's possible to find an algorihm that runs in $2^{O(n)}$ or not. – Jinx Nov 5 '13 at 15:06
• I'm thinking of doing gift wrapping in $n+1$ dimensions, since we don't have to store previous results with gift wrapping. If we can somehow bound the number of open ridges, then the space would not be too big. – Jinx Nov 5 '13 at 15:17