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$.

So for any set of points in any dimension, it's possible to find the Delaunay edges one by one, by solving a number of linear programs that is polynomial in the number of points. The reason Delaunay triangulation is hard is not because of the edges, it's because there may be too many higher-dimensional features.

| cite | improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – Jinx Nov 5 '13 at 3:17
  • $\begingroup$ The idea of lifting to one dimension higher is extremely standard when working with Delaunay triangulations. And I'm confused by your followup question: doesn't the algorithm I just described find them all in polynomial time and polynomial space? $\endgroup$ – David Eppstein Nov 5 '13 at 6:29
  • $\begingroup$ 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. $\endgroup$ – Jinx Nov 5 '13 at 15:06
  • $\begingroup$ 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. $\endgroup$ – Jinx Nov 5 '13 at 15:17
  • 1
    $\begingroup$ Oh, I see what you mean. The ellipsoid method for linear programming runs in polynomial time given only a separation oracle (a black box that can tell whether a point is inside or outside the feasible polytope, and if outside returns a separating hyperplane). See "Geometric Algorithms and Combinatorial Optimization" by Grötschel, Lovász, and Schrijver. And in the parallelotope case, such an oracle is easy to implement in low space — just loop through all the parallelotope vertices testing each one. So I think the answer is yes, this same algorithm runs in polynomial space in terms of n. $\endgroup$ – David Eppstein Nov 5 '13 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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