2
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ I'd be very surprised if there is a general formula (the problem reeks of optimization), but an algorithm should be possible to construct. $\endgroup$
    – Bobson Dugnutt
    Oct 11, 2016 at 19:53
  • $\begingroup$ "...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? $\endgroup$
    – Larry B.
    Oct 11, 2016 at 20:01
  • $\begingroup$ @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. $\endgroup$
    – Paul Terwilliger
    Oct 11, 2016 at 20:03
  • $\begingroup$ how would you do this in a segment of length one? dimension 1 rather than 3 $\endgroup$
    – Will Jagy
    Oct 11, 2016 at 20:12
  • $\begingroup$ @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. $\endgroup$
    – Paul Terwilliger
    Oct 11, 2016 at 20:15

1 Answer 1

Reset to default
5
$\begingroup$

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.

enter image description here

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

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

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.