<p>I have a set of vertices <span class="math-container">$V\subset\mathbb R^3$</span> and a set of edges <span class="math-container">$S=\{(a,b)|a,b \in V\}$</span>. I want to know whether an edge in the set <span class="math-container">$S$</span> is Delaunay against the vertices in <span class="math-container">$V$</span>. </p>

<p>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.</p>

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

<p><strong>UPDATE:</strong> Answer to a question <a href="https://cstheory.stackexchange.com/a/19663/21170">here</a> models Delaunay-edge criteria as a linear programming feasibility problem. Concisely, it searches for a vector, scalar tuple <span class="math-container">$(v,c)$</span> such that for a set of vertices <span class="math-container">$P$</span>(formed by transforming original points <span class="math-container">$(x,y,z)$</span> in 3D space to <span class="math-container">$(x,y,z,x^2+y^2+z^2)$</span> in 4D space) and endpoints of a  Delaunay edge candidate <span class="math-container">$(p_i,p_j)\in P$</span>,</p>

<p><span class="math-container">$v.p_a \geq c$</span></p>

<p><span class="math-container">$v.p_b=c$</span></p>

<p>where <span class="math-container">$p_a\in P-\{p_i,p_j\}$</span> and <span class="math-container">$p_b\in\{p_i,p_j\}$</span></p>

<p>and it recommends using <em>ellipsoid method</em>, but <a href="http://en.wikipedia.org/wiki/Ellipsoid_method#Performance" rel="nofollow noreferrer">Wiki section</a> on this method describes it as numerically unstable beyond 2 dimensions. Is there any other <em>practical</em> yet numerically stable(in three dimensions) linear programming approach for performing Delaunay edge test?</p>

<p>P.S.: I have already asked this question on <a href="https://cs.stackexchange.com/questions/24215/practical-algorithm-for-testing-whether-an-edge-is-delaunay">ComputerScience SE</a> but did not receive any relevant response.</p>

CC BY-SA 3.0
2014-05-15T17:52:17.033Z
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
CC BY-SA 3.0
2014-05-16T14:52:28.840Z
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
CC BY-SA 3.0
2014-05-20T11:48:02.063Z
@GeoffreyIrving ah that's true. For some reason I only just saw your comment.
Suresh Venkat
CC BY-SA 3.0
2014-05-21T04:15:03.850Z
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. http://www.mpi-inf.mpg.de/departments/d1/teaching/ss10/opt/handouts/lecture25-SeidelLinearProgramming.pdf
David Eppstein
CC BY-SA 3.0
2014-05-21T06:53:03.600Z
@DavidEppstein In your [response](http://cstheory.stackexchange.com/a/19663/21170), 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
CC BY-SA 3.0
2014-05-21T06:55:01.540Z
@DavidEppstein Actually, data points(vertices) in my problem come from a [3D scanner](http://en.wikipedia.org/wiki/3D_scanner) and are typically on the order of millions. So my problem is **low-dimensional** but with **many constraints**.
Pranav
CC BY-SA 3.0
2014-05-21T21:34:33.387Z
Low-dimensional with many constraints is not a problem. The better of the low-dimensional linear programming algorithms have time bounds like $O(d^2 n + f(d))$ for some non-polynomial function $f$; see e.g. Matoušek, Sharir, and Welzl, Algorithmica 1996. The problem raised by the other question was to achieve space substantially less than #constraints for a computation where the constraints were implicit rather than being part of the input. As for features: triangles, tetrahedra, etc.
David Eppstein
<ds.algorithms><cg.comp-geom><linear-programming>
Practical algorithm for testing whether an edge is Delaunay
Pranav
# Practical algorithm for testing whether an edge is Delaunay

(Asked by: username_0 on 2014-05-15)

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](https://cstheory.stackexchange.com/a/19663/21170) 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](http://en.wikipedia.org/wiki/Ellipsoid_method#Performance) 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](https://cs.stackexchange.com/questions/24215/practical-algorithm-for-testing-whether-an-edge-is-delaunay) but did not receive any relevant response.

**Tags:** ds.algorithms, cg.comp-geom, linear-programming

> **Comments:**
> **username_1**: 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.  
> **username_1**: 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.  
> **username_2**: @GeoffreyIrving ah that's true. For some reason I only just saw your comment.  
> **username_3**: 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. http://www.mpi-inf.mpg.de/departments/d1/teaching/ss10/opt/handouts/lecture25-SeidelLinearProgramming.pdf  
> **username_0**: @DavidEppstein In your [response](http://cstheory.stackexchange.com/a/19663/21170), 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.  
> **username_0**: @DavidEppstein Actually, data points(vertices) in my problem come from a [3D scanner](http://en.wikipedia.org/wiki/3D_scanner) and are typically on the order of millions. So my problem is **low-dimensional** but with **many constraints**.  
> **username_3**: Low-dimensional with many constraints is not a problem. The better of the low-dimensional linear programming algorithms have time bounds like $O(d^2 n + f(d))$ for some non-polynomial function $f$; see e.g. Matoušek, Sharir, and Welzl, Algorithmica 1996. The problem raised by the other question was to achieve space substantially less than #constraints for a computation where the constraints were implicit rather than being part of the input. As for features: triangles, tetrahedra, etc.  

---

## 0 answers

