# Practical algorithm for testing whether an edge is Delaunay

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

$$v.p_b=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.

• 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. – Geoffrey Irving May 15 '14 at 17:52
• 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. – Geoffrey Irving May 16 '14 at 14:52
• @GeoffreyIrving ah that's true. For some reason I only just saw your comment. – Suresh Venkat May 20 '14 at 11:48
• 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/… – David Eppstein May 21 '14 at 4:15
• @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. – Pranav May 21 '14 at 6:53