Number of nodes for empty space vs. data

[Sebastian Wouters]

Hello,

(This mail follows a short private discussion with Armin Hornung and Wolfram Burgard.)

For a sphere represented with increasingly finer voxels, it appears that the number of nodes (intermediate and leaf) to represent the empty space ("inside" of the sphere) divided by the number of nodes (intermediate and leaf) to represent the data ("boundary" of the sphere) converges to a constant. (The boundary needs to be represented fine-grained, whereas the inside can be represented with larger nodes if its entire volume is empty space, cfr. doi: 10.1007/s10514-012-9321-0).

I've encountered this during numerical experiments in the summer of 2020 (see cpp attached), and I also have a mathematical estimate of both respective numbers and their fraction (see pdf attached) in three dimensions.

It appears that the fraction inside/boundary decreases with increasing dimension:

0.84 for dimension 2

0.64 = 9/14 for dimension 3

0.56 for dimension 4

Best regards,

Sebastian

PS: In the meantime I also have N(boundary) for general dimension d in the notation of the pdf:

N(boundary) = \frac{2^d * d}{d-1} \left( \prod_{k=0}^{d-3} \frac{\sqrt{\pi}}{2} \frac{\Gamma(\frac{1}{2} + \frac{k}{2})}{\Gamma(1 + \frac{k}{2})} \right) \left( \frac{r}{b} \right)^{d-1} \frac{2^{n(d-1)}}{2^{d-1} - 1}.

PS2: I guess that as long as the number of "rips" is limited, and you hence don't go towards some fractal surface, the essence of the result won't be changed. You will always reach a voxel size where for the majority of voxels the surface appears smooth and flat.