# 3D Space Covering-Problem

Given a finite amount of "slots" in 3D space, e.g.

$$S = [(1,2,3),(1,3,3),(1,4,3),(1,3,4)] \in \mathbb{N}^3.$$

I'm trying to find an efficient algorithm to determine a minimal set of (rectangular) cuboids $B$ that cover all slots. E.g. a non minimal solution for the example above would be

$$B = \{\{S_1,S_3\}, \{S_0\}, \{S_2\}\}$$

and a minimal solution would be

$$B = \{\{S_0, S_1, S_2\},\{S_3\}\}.$$

An algorithm that converges would be preferred. Surely there has been some research on this already. I'd be very happy if someone could point me into the right direction!

• Can you explain a "slot" is, and what it means for a cuboid to cover a slot? At first I interpreted them as points in $\mathbb R^3$, but that makes the question trivial. – Rahul Feb 16 '14 at 23:12
• Sorry, I should have clarified. A slot is an available cube with center as defined and edge length one. – vincent Feb 17 '14 at 0:48