# Finding the farthest point within a cube from a set of $n$ other points

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?

• I'd be very surprised if there is a general formula (the problem reeks of optimization), but an algorithm should be possible to construct. Oct 11, 2016 at 19:53
• "...until the volume of the cube $C$ is entirely occupied by the combined volumes of each sphere $s_i$" What do you mean by "entirely occupied"? Does this mean that, if I put a point in the center, since it's the furthest from the cube's corners, that's the "furthest" point? Oct 11, 2016 at 20:01
• @LarryB. If the set of points $n$ has no elements, then there would be no furthest point. My definition of furthest requires the set of points $n$ to have at least one entry. If the set of points $n$ has exactly one point at the origin, then each vertex would equally be furthest. If the set of points $n$ has one point at every vertex of the cube, then the origin would be furthest. These are some trivial examples. Oct 11, 2016 at 20:03
• how would you do this in a segment of length one? dimension 1 rather than 3 Oct 11, 2016 at 20:12
• @WillJagy Every two neighboring points has a midpoint. Find the midpoint that has the longest distance from either neighbor. Include the points (at the edge) of the segment in the set of midpoints. So, in a sense, my question is about trying to minimize how close it is to any one point while staying within bounds. Oct 11, 2016 at 20:15

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$.

• Splendid animation. Can you say which software you have used ? Oct 11, 2016 at 21:44
• I did an image search for "voronoi diagram" and restricted the search to animated GIFs. This was one of the first search results. Oct 11, 2016 at 21:58