PARTITIONING 3D PHANTOMS INTO HOMOGENEOUS CUBOIDS
Anuj Jain, Sartaj K. Sahni, Jatinder R Palta, J.F. Dempsey · International Journal of Foundations of Computer Science · 2003
We analyze the heuristic proposed by Jung [3] to partition a 3D phantom into homogeneous cuboids. We show that the 2D version of this heuristic generates the minimum number of rectangles when partitioning 2D non-degenerate phantoms. However, this 2D version doesn't generate optimal partitions of degenerate 2D phantoms. In fact, the heuristic may generate more than 3 times as many rectangles as is necessary. The 3D heuristic of [3] doesn't generate optimal partitionings of 3D simple phantoms either. We show that slicing partitions of 3D simple phantoms are optimal. Our analysis suggests a new heuristic for 3D phantoms. This heuristic generated one-third as many cuboids when used to partition a 3D CT-scan phantom and about one-fourth as many cuboids on randomly generated 3D phantoms as produced by the heuristic of [3].