Sparse Multi-Dimensional Data Representation

Question

I'm working on a cardiac simulation tool that uses 4-dimensional data, i.e. several (3-30) variables at locations in 3D space.

I'm now adding some tissue geometry which will leave over 2/3 of the points in the containing 3D box outside of the tissue to be simulated, so I need a way to efficiently store the active points and not the others.

Crucially, I need to be able to:

• Iterate over all of the active points within a constrained 3D box (iterator, perhaps?)
• Having accessed one point, find its orthogonal neighbours (x,y,z) +/- 1.

That's probably more than one question! My main concern is how to efficiently represent the sparse data.

I'm using C.

Answer 1

How often do you add the tissue, and how much time can it take?

One simple solution is using a linked list+hash with pointers from one to the other.

Meaning:

1. Save a linked list containing all of the relevant points and their data
2. Save a hash to easily get to this data: key = coordinates, data = pointer to the linked list.

The implementation of the operations would be:
Add a box: Go over the full linked list, and take only the relevant elements into the "work" linked list
Iterate: Go over the "work" linked list
Find neighbors: Seek each of the neighbors in the hash.

Complexity:
Add: O(n), Iterate O(1) for finding next element, Neighbor O(1) average (due to hash).