According to Wikipedia 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?

  • 1
    $\begingroup$ 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}? $\endgroup$ – David Eppstein Mar 13 '13 at 16:18
  • $\begingroup$ @DavidEppstein I've rephrased my question. I hope it's clearer now. $\endgroup$ – Deathbreath Mar 13 '13 at 20:13
  • 3
    $\begingroup$ 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? $\endgroup$ – David Eppstein Mar 13 '13 at 21:07
  • 2
    $\begingroup$ I don't know about the connection to Delaunay tessellations, but presumably "largest" might even just be the cardinality of the set ? $\endgroup$ – Suresh Venkat Mar 14 '13 at 0:21
  • 2
    $\begingroup$ More notation does not make things "more mathematical". Edited for clarity. $\endgroup$ – Jeffε Mar 15 '13 at 3:52

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:


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.

  • $\begingroup$ 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".) $\endgroup$ – Jeffε Jul 26 '13 at 3:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.