This is (it seems to me) a well-known fact, but I am struggling to find a reference.
Let $X=\{x_1,\dots, x_n\}\subset \mathbb R^d$ be a set of points. Then the following is true:
Subset $F\subset X$, with $\mathrm{card}F=k+1$, forms a $k$-face of the Delaunay triangulation of $X$ iff there exists an empty $d$-dimensional sphere on which all points of $F$ lie.
I am interested specifically in the case $d=3,k=1$, i.e. an edge of Delaunay tetrahedrization. If you only provide a reference for this case, I will accept it as an answer.
I only found some proofs of the case $d=2,k=1$ and then a number of people using this fact without a source.
Is there a reference for this fact? Or is the proof in fact so elementary that there simply is no reference?
I am unaware of a complete proof in the literature. The result is elementary and conceptually straightforward but isn't particularly concise.
The main idea in the proof is that if we have an empty ball with a particular $k$-face on its boundary, we can grow or shrink the ball until it touches an additional point in $X$ in a way that keeps the $k$-face on the boundary. This is repeated until we find a ball that ensuring the existence of a Delaunay simplex containing the original $k$-face.
Suppose $X$ is a finite point set containing at least $d+1$ points in general position. Let $F \subset X$ be a $k$-face and let $B(c, r)$ be a ball with $F \subset \partial B(c, r)$ and $B(c,r) \cap X = \emptyset$.
Defining $c_F$ to be the circumcenter of $F$ and $r_F$ to be the circumradius of $F$, consider the family balls $B(c_F + tv, r_t)$ where $r_t = \sqrt{r_F^2 + t^2}$ and $v = \frac{c-c_F}{|c-c_F|}$. If $c_F = c$, this direction is not defined but we can let $v$ be any unit vector orthogonal to $F$.
Now we will consider the range of $t$ values for which $B(c_F + tv, r_t)$ is empty. Since $c = c_F + |c-c_F| v$, there exists some $t$ for which the ball is empty. Formally,
$$t_- = \inf\, \{ t : B(c_F + tv , r_t) \cap X = \emptyset \},$$
and
$$t_+ = \sup\, \{ t : B(c_F + tv , r_t) \cap X = \emptyset \}.$$
Both $t_-$ and $t_+$ cannot be both infinite, otherwise all points of $X$ belong to a hyerplane containing $F$ violating our assumption of general position. Without loss of generality suppose $t_+$ is finite. Now $B(c_F + t_+v , r_{t_+})$ must contain some $x_j\in X \setminus F$ on its boundary (otherwise we could perturb $t$ and the ball would continue to be empty).
If $k = d-1$, then $F\cup \{x_j\}$ is a Delaunay simplex ensuring that $F$ is a $k$-face in the Delaunay triangulation. If $k < d-1$, we have simplex $F' = F\cup\{x_j\}$ and a new empty ball $B(c_F + t_+v , r_{t_+})$ and can repeat the above process for $F'$ until we reach a full dimensional Delaunay simplex.