W Randolph Franklin home page
... (old version)
Research/ home page Login


(back to Connected Components main page)

Intro

The next major test series is a set of random volumes, with each voxel independently full or empty with a given probability. The goal is to get an intuitive feeling for the connectivity of random universes. Altho actual data will generally show correlations, this random analysis may still be of interest.

The method is as follows. All the steps described below are pipelined together.

  1. Generate a desired number of pseudo-random bytes thus:
    head -c N /dev/urandom
  2. Threshhold the bytes to be either '0' or '1', making any byte less than or equal to the given value to be 0.
  3. Use char2bit to pack the bytes into bits.
  4. Run a modified version of connect2 that writes only the number of components, appending it to a file in ncomps/USIZE/CONN/THRESH

Another version, for p=50%, generated the voxel bits directly, w/o generating bytes and threshholding.

Consistency of Component Numbers

The first question is, if several different random volumes are connected, are the numbers of components similar? We ran 100 tests for each of 10 universe sizes, all with the probability of an empty voxel being 0.5. Things are well behaved.

26-connectivity is less interesting here, since with p=0.5, there is usually only one component.

Numbers of Components for Various Fill Factors

The next question is, how many components are generated for various universe sizes and fill factors (probability that a voxel is empty)? We did 10 runs each for many combos of universe sizes and fill factors for 6-connectivity. Then we did 1 run each for some combos of sizes and fill factors for 26-connectivity. The following figure shows the results. The error bars for the 6-connectivity are 1 sigma to each side of the mean. The 26-connectivity cases are the curves scrunched to the left.

We observe that the fill factor giving the maximum number of components is independent of the universe size. For 6-connectivity, p=.2 (approx), gives the most components. For 26-connectivity, p=0.5 does. This independence is reasonable since connectivity is a local property.

Component Sizes Versus Fill Factors

We then re-analyzed the above data to show component size (volume) depended on universe size and fill factor. The lower group of lines is 6-connectivity, while the upper group, which does not extend all the way to the right, is 26-connectivity. The 26-connectivity lines are more irregular since we ran fewer cases.

For component sizes much smaller then the universe size, the universe size was irrelevant, which is reasonable. The limiting case for a fill factor approaching 1 is one component whose size is the universe's volume.

It's not clear what the functional relationship is. In one dimension, component sizes (lengths) would be exponentially randomly distributed, with mean length=(1/(1-p)). However, here in 3D, neither the component volumes nor their lengths appear to follow this. This suggests an area for theoretical work.