Delaunay Triangulation of Parallelepiped
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.