# Subdivision Data Structures

# 1 Vector Of Coordinates

Store the subdivision level and count of boxes. For each box, store x,y coordinates as fixed width integers.

Maximum depth is limited by width of coordinates.

Real coordinates are implied by external context.

For-each mapping is trivial, even in parallel (atomic counter for input).

Subdivision is trivial, even in parallel (two atomic counters for input and output, out of order output does not matter).

Uniform sampling is trivial.

Space efficiency is terrible (see below).

# 2 Vector Of Bitmaps

Suggested by tavis on fractalforums.org.

Store the subdivision level and count of groups. For each subdivided group of 8x8 boxes, store x,y coordinates as fixed width integers, and each box as 1 bit in an 8x8 bitmap (64 bits).

Maximum depth is limited by width of coordinates, plus 3.

For-each mapping is slightly more complicated, but can be parallelized.

Subdivision likewise.

Efficient uniform sampling requires additional data (like a cumulative distribution table).

Space efficiency is good (see below).

# 3 Bit-Packed Quad Tree

Store the subdivision level and count of bits. At this level, 0 correponds to empty and 1 to populated leaf. At levels closer to the root, 0 corresponds to empty and 1 to node with branches: four subtrees follow.

Maximum depth is practically unlimited (32bit bit count may overflow if data exceeds 32GB, but 64bit bit count should be good for a while).

For-each mapping is now naturally based on a recursive function, and efficient parallelism is very hard.

Subdivision likewise.

Efficient uniform sampling is also not feasible.

However, space efficiency is excellent (see below).

# 4 Space Efficiency

For subdivision of lower half of Mandelbrot set boundary to effective level 13, with 593490 boxes:

Other input data (e.g. perhaps sparse Cantor dust) may give different results.