# Find the largest empty space inside a cube populated with a point cloud?

Lets say we have a set of points (x, y, z) where we know 0 < x < 1 (same for y and z). Now that 3d space is populated with monsters, players or what not. The points represent their location. We want to find the largest vacant 3d space. What would be an effective algorithm to find, let's say, the k largest disjoint empty boxes inside that space?

I was thinking of using Voronoi Diagram and measuring the space near each seed (the points being the seeds) and looking for pairs of neighbors that have a large space.

• What are the rules for defining the concept of "empty space" in your context? That is, how do two different "empty space" regions know they're separate? The question is potentially very interesting, but I think it needs this extra bit of clarification to benefit from correct answers. Mar 1, 2015 at 15:00
• Well, in the case I described, it's a box (not axis aligned) that does not contain any of the points. I don't actually want a box. Any convex 3d shape would be fine. I just figure a box is simpler. It wouldn't be bad to generalize it and find the largest k disjoint boxes that contain only m points (where m is very small). Mar 1, 2015 at 15:20
• If you restrict it to the largest convex space, you might be able to use a greedy approach whereby you delete points from the convex hull which reduce its size the least, take the convex hull of that, and keep iterating until there are no more points inside the hull (only on the surface). A similar approach could be used for the larges bounding box. Mar 1, 2015 at 22:05
• Note that if there are no restrictions like convexity, this problem is ill-formed, because the largest empty space is trivially the unit cube minus the points in the point set. Mar 1, 2015 at 22:06
• Another thing you could do is voxelize the cube to some resolution, and then do a flood fill of all the voxels that contain no points. The connected components of this flood fill are the empty regions. Mar 1, 2015 at 22:11

EDIT:

My first approach is still below, but I found a problem with it. If the large empty region is on a border (outside the convex hull of your points), it won't be detected. Putting points on the border like I did with the corners doesn't help because the triangles can be made bouncing from your points to those new points.

Another approach, which ought to work but might be too expensive to compute, is to generate a mesh of evenly spaced points across the space and use a nearest neighbors algorithm on each of the points in this mesh to find the point from your original points that's closest. The mesh point that is most distant from anything is the center of the biggest empty region.

I don't know how to find the second most empty region.

Then you can do a Delaunay triangulation (this the dual of Voronoi diagram) in 3 dimensions. (The library call in Python is scipy.spatial.Delaunay.)
Go through all the triangles (in 3 dimensions, these are tetrahedrons) and calculate their volume. (The library call in Python is scipy.spatial.ConvexHull.volume.) I think these are your biggest empty spaces, or if they're not, it's at least an indicator of a big empty space.