I have a cube $C$ in 3 dimensions. The length of each side is 1, and it is centered at the origin. I have a set of $n$ points within the volume of this cube. I am trying to find the point $p$ within the volume of this cube that is the farthest from all $n$ points. I define farthest using the following procedure:
Imagine that each of the $n$ points is represented by a sphere $s_i$ (where $0 \leq i \leq n$) of radius $r = 0$ at their location in 3-dimensional space. Imagine that the radius $r$ of each sphere gradually grows until the volume of the cube $C$ is entirely occupied by the combined volumes of each sphere $s_i$. What is the last point/s in the volume to be occupied? This is the farthest.
Is there a general formula for this?
Construct a three-dimensional Voronoi diagram out of the set of $n$ points. You can see from the animation of a two-dimensional Voronoi diagram's "growing sphere" visualization. Let this motivate the solution below.
Each point $x_i$ will be associated with a convex Voronoi polyhedron $P_i$, for which the points within that polyhedron are closest to that point. Since $P_i$ is convex, its vertices $V(P_i)$ are the furthest points which are closest to $x_i$. Note: These aren't strictly $P_i$, but really the intersection of $P_i$ and the cube. Since we are taking the intersection of two convex polyhedra, the result is still convex.
Let $p_i$ be the point in $V(P_i)$ with the maximum distance from $x_i$, and choose $p$ to be the $p_i$ with the greatest distance from its respective $x_i$.