# Delaunay tesselations and convex hulls

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?

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