Data structure for representing overlapping abstract sets in the style of Venn Diagrams?

I've got a bunch of abstract sets which may overlap with each other in arbitrary ways. If a given set were either completely contained by another set, or does not overlap with the other set at all, then I could easily store the relationship as a forest of sets, where for each tree, the parent set contains the child set. Unfortunately, it's possible for these sets to partially overlap; that is, their interception can be non-empty, but neither set is a subset of the other.

The query I'm primarily interested in is determining for a given set, what other set can its members possibly belong to (i.e. what other set does this set overlap with).

I suppose I could just build a huge table, and for every pair of sets, state whether one contains the other, or if they partially overlap, or if they are completely distinct, but it seems like there would be a lot of redundant data in that table (e.g. it doesn't exploit the transitivity of containment of sets, so that if set A contains set B and set B contains set C, set A contains set C).

Any ideas on what kind of data structure would be optimal for representing this data?

- Oliver

.

Relevant Pages