XLVII
December 8, 2021, 11:57am
#1
```
Let S = { trigon, tetragon , pentagon , ... ,... } is a set of polygons
```

How to calculate intersection of subsets of (every element actually) `Powerset(S)`

```
Powerset(S) =[ {} , {trigon} , {tetragon} , {pentagon} , {trigon, tetragon} , {trigon,pentagon} ,......]
for i in Powerset(S)
find intersect(i)
```

I need really fast algorithm, is there any solution?
intersection funtion is so expansive and therefore I want minimize this

Are dynamic programming solutions suitable for this?

find every node intersection

intersect( a, b,c ) = intersect( intersect ( a,b), c)

Dynamic programming will help a lot here, but the much better method is to not do this in the first place. This operation inherently has exponential time relative to the number of polygons.

XLVII
December 8, 2021, 3:00pm
#3
Can you say something about time complexity?

`S`

is a set with `2^n`

elements in it. You want to allocate an object for each of those. That’s a ton of time if n isn’t very small (less than 15 or so)