<p>The relationship I remember is that the Delaunay tessalation is the "visual complement" of Voronoi cells.</p>

<p>I just found this paper on Google which has a nice figure as to why finding the convex hull in d+a dimensions is equivalent to finding the Delaunay tessalation:</p>

<p><a href="http://www.cs.mtu.edu/~shene/PUBLICATIONS/2004/Hull2VD.pdf" rel="nofollow">http://www.cs.mtu.edu/~shene/PUBLICATIONS/2004/Hull2VD.pdf</a></p>

<p>What's also interesting from a theoretical cs perspective is that the knn problem can be mapped to the Voronoi cell problem, and by extension to the Delaunay tesselation and the convex hull problem. Known algorithms in d-dimensions typically have an exponential dependency on dimension.</p>

CC BY-SA 3.0
2013-07-26T03:28:51.680Z
This does not answer the stated question.  (And the word you're looking for for the relation between Delaunay tessellations and Voronoi diagrams is "dual".)
Jeffε
CC BY-SA 3.0
2013-07-25T18:12:32.533Z
2013-07-25T18:19:21.090Z
2013-07-25T18:19:21.090Z
Phil
<p>According to <a href="http://en.wikipedia.org/wiki/Delaunay_tessellation" rel="nofollow">Wikipedia</a> the Delaunay tesselation in $d$ dimensions can be viewed as a convex hull problem in $d+1$ dimensions. Given a countable set of points $S\subset \mathbb{R}^d$ and a point $p\in S$, find the largest subset $X\subset S\setminus\{p\}$ with the following properties:</p>

<ul>
<li><p>Every point in $X$ is a vertex of the convex hull of $X$.</p></li>
<li><p>$p$ is the only point in $S$ that lies in the interior of the convex hull of $X$. </p></li>
</ul>

<p>Is there a relationship between the $d$-dimensional Delaunay tesselation and the set of polytopes for each point $p\in S$ as described?</p>

CC BY-SA 3.0
2013-03-13T16:18:30.490Z
Please express this more clearly. What do you mean for a polytope to be "in" a set of points? Is it the set or the polytope that is "around P" and what does that mean? What object do you want to "only contain P", and what does that mean for something that is not the singleton set {P}?
David Eppstein
CC BY-SA 3.0
2013-03-13T20:13:18.833Z
@DavidEppstein I've rephrased my question. I hope it's clearer now.
Deathbreath
CC BY-SA 3.0
2013-03-13T21:07:05.773Z
Quite a bit better, but what do you mean by "largest"? (Volume?) And why do you expect that there is a relationship between this problem and Delaunay or convex hulls?
David Eppstein
CC BY-SA 3.0
2013-03-14T00:21:47.247Z
I don't know about the connection to Delaunay tessellations, but presumably "largest" might even just be the cardinality of the set ?
Suresh Venkat
CC BY-SA 3.0
2013-03-14T12:04:34.813Z
@DavidEppstein I was thinking (hyper)volume, but cardinality of set seems a more valuable concept. I suspect that in 2/3D a tesselation derived from this concept generally coincides with (Euclidean) Delaunay.
Deathbreath
CC BY-SA 3.0
2013-03-14T15:25:05.930Z
I tried to encode the problem more mathematically.
Deathbreath
CC BY-SA 3.0
2013-03-15T03:52:34.663Z
More notation does not make things "more mathematical".  Edited for clarity.
Jeffε
CC BY-SA 3.0
2013-03-17T02:12:13.813Z
No. The two things seems unrelated.
Sariel Har-Peled
<cg.comp-geom>
Delaunay tesselations and convex hulls
Deathbreath
# Delaunay tesselations and convex hulls

(Asked by: username_0 on 2013-03-13)

According to [Wikipedia](http://en.wikipedia.org/wiki/Delaunay_tessellation) the Delaunay tesselation in $d$ dimensions can be viewed as a convex hull problem in $d+1$ dimensions. Given a countable set of points $S\subset \mathbb{R}^d$ and a point $p\in S$, find the largest subset $X\subset S\setminus\{p\}$ with the following properties:

* Every point in $X$ is a vertex of the convex hull of $X$.
* $p$ is the only point in $S$ that lies in the interior of the convex hull of $X$.

Is there a relationship between the $d$-dimensional Delaunay tesselation and the set of polytopes for each point $p\in S$ as described?

**Tags:** cg.comp-geom
> **Comments:**
> **username_1**: Please express this more clearly. What do you mean for a polytope to be "in" a set of points? Is it the set or the polytope that is "around P" and what does that mean? What object do you want to "only contain P", and what does that mean for something that is not the singleton set {P}?  
> **username_0**: @DavidEppstein I've rephrased my question. I hope it's clearer now.  
> **username_1**: Quite a bit better, but what do you mean by "largest"? (Volume?) And why do you expect that there is a relationship between this problem and Delaunay or convex hulls?  
> **username_2**: I don't know about the connection to Delaunay tessellations, but presumably "largest" might even just be the cardinality of the set ?  
> **username_0**: @DavidEppstein I was thinking (hyper)volume, but cardinality of set seems a more valuable concept. I suspect that in 2/3D a tesselation derived from this concept generally coincides with (Euclidean) Delaunay.  
> **username_0**: I tried to encode the problem more mathematically.  
> **username_3**: More notation does not make things "more mathematical".  Edited for clarity.  
> **username_4**: No. The two things seems unrelated.  

---

## 1 answers

### Answer by username_5 on 2013-07-25. Score: -2

The relationship I remember is that the Delaunay tessalation is the "visual complement" of Voronoi cells.

I just found this paper on Google which has a nice figure as to why finding the convex hull in d+a dimensions is equivalent to finding the Delaunay tessalation:

<http://www.cs.mtu.edu/~shene/PUBLICATIONS/2004/Hull2VD.pdf>

What's also interesting from a theoretical cs perspective is that the knn problem can be mapped to the Voronoi cell problem, and by extension to the Delaunay tesselation and the convex hull problem. Known algorithms in d-dimensions typically have an exponential dependency on dimension.

> **Comments:**
> **username_3**: This does not answer the stated question.  (And the word you're looking for for the relation between Delaunay tessellations and Voronoi diagrams is "dual".)  

---

