I have a set of vertices $V\subset\mathbb R^3$ and a set of edges $S=\{(a,b)|a,b \in V\}$. I want to know whether an edge in the set $S$ is Delaunay against the vertices in $V$.

My assumed definition of a Delaunay edge is: An edge is Delaunay, iff there exists a circumsphere of its endpoints not containing any other vertex inside it.

I would like to know practical approaches/algorithms for such Delaunay-edge test.

UPDATE: Answer to a question here models Delaunay-edge criteria as a linear programming feasibility problem. Concisely, it searches for a vector, scalar tuple $(v,c)$ such that for a set of vertices $P$(formed by transforming original points $(x,y,z)$ in 3D space to $(x,y,z,x^2+y^2+z^2)$ in 4D space) and endpoints of a Delaunay edge candidate $(p_i,p_j)\in P$,

$v.p_a \geq c$


where $p_a\in P-\{p_i,p_j\}$ and $p_b\in\{p_i,p_j\}$

and it recommends using ellipsoid method, but Wiki section on this method describes it as numerically unstable beyond 2 dimensions. Is there any other practical yet numerically stable(in three dimensions) linear programming approach for performing Delaunay edge test?

P.S.: I have already asked this question on ComputerScience SE but did not receive any relevant response.

  • 1
    $\begingroup$ Easy special case: If $|S| = 1$ in two dimensions this takes $O(n)$ by finding the closest vertices to $S$ on either side in the circumcircle order. $\endgroup$ May 15, 2014 at 17:52
  • 1
    $\begingroup$ Suresh: Isn't that sufficient but not necessary? For example, all convex hull edges are Delaunay, regardless of how close points get to them on the inside. $\endgroup$ May 16, 2014 at 14:52
  • $\begingroup$ @GeoffreyIrving ah that's true. For some reason I only just saw your comment. $\endgroup$ May 20, 2014 at 11:48
  • 1
    $\begingroup$ The answer you link to suggested ellipsoid for a very specific reason (keeping space small in a problem with many constraints) that does not apply here. For this one, standard low-dimensional LP algorithms such as Seidel's $O(d! n)$ one should work just fine. See e.g. mpi-inf.mpg.de/departments/d1/teaching/ss10/opt/handouts/… $\endgroup$ May 21, 2014 at 4:15
  • $\begingroup$ @DavidEppstein In your response, I would like to know which features you are referring to in the last statement "...because there may be too many higher-dimensional features.". Unfortunately, currently I don't have enough rep to comment directly there. $\endgroup$
    – Pranav
    May 21, 2014 at 6:53


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.