The Art Gallery Guardian

Two problem related to sequence of sets


Given a sequence of sets \(S_1,\ldots,S_n\). \(\sum_{i=1}^n |S_i|=m\). The elements in the sets are ordered. We are interested in the following problems

Problem1

Decide if there exist \(i\neq j\) such that \(|S_i\cap S_j|\geq k\).

For \(k=0,1\), we can solve it in \(O(m \log m)\) time: Take the union and see if there is any repeats. This goes to element distinctness problem.

For larger \(k\), we look through each element, and find all sets containing that element(this can be done in \(O(m\log m+nm))\) time). For each pair of sets containing that element, say if \(i,j\) are such pair, we increment a counter in \(D[i,j]\). Then we look through the table until we find a position where \(D[i,j]\geq k\). Total this is a \(O(m\log m+nm)\) time algorithm. One can improve the running time when \(n\) is large by reduce it to a similar problem of finding rectangles.

Problem2

Partition \([n]\), such that if \(i,j\) is in the same partition, then \(S_i=S_j\).

The idea is basically build a trie for the bit vector representation of the sets. Except we will be a bit more clever and skip all the \(0\) elements. We should get a \(O(m\log m)\) time algorithm.

Posted by Chao Xu on 2015-02-08.
Tags: algorithm.