Is there a data structure like the union-find data structure, but for intersections (and the sets needn't be disjoint)?(adsbygoogle = window.adsbygoogle || []).push({});

I'm looking for a data structure that stores an indexed set of sets A_1, A_2, ..., A_n, and supports the following operations:

replace the sets A_i, A_j with their intersection A_i n A_j, in sub-linear time, and returns the index of the intersection thus formed.

given the index of a set, list its contents in linear time

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Intersection-find Data Structure

**Physics Forums | Science Articles, Homework Help, Discussion**