Say we have the letters $\Omega = \{1,2,\dots n\}$, and two sets of subsets of $\Omega$, $S_1, S_2$.
I want to find $S_1 \cdot S_2 := \{(s_1,s_2) \in S_1 \times S_2: s_1 \cap s_2 = \emptyset \}$. With the sets I'm working with, the cardinality of $|S_1 \cdot S_2|$ should be considerably smaller than $|S_1||S_2|$, thus I was wondering if there's a better solution. Is there an efficient data structure, which after preptime, can generate $S_1 \cdot S_2$, in $O(|S_1 \cdot S_2|+n^c)$ time? (so it takes polynomial time to create to encodes the pairings, and then constant time to return each pairing) I'd imagine there'd be a smart way to do this with posets, but a concrete structure eludes me currently.
If so, is there a way to be able to quickly update our structure, allowing us to add supersets of elements like so:
$$S_1 = S_1 \cup \{f(s_1,s_2) \supset s_1, \forall (s_1,s_2) \in S_1 \cdot S_2 \}$$ $$ S_2 = S_2 \cup \{ g(s_1,s_2) \supset s_2, \forall (s_1,s_2) \in S_1 \cdot S_2\}$$
with complexity $O(n^c|S_1 \cdot S_2|)$, where $f$ and $g$ are some arbitrary functions with the stated superset properties?
