# 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. – teodron Mar 1 '15 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). – wolfdawn Mar 1 '15 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. – mklingen Mar 1 '15 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. – mklingen Mar 1 '15 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. – mklingen Mar 1 '15 at 22:11